※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
$n=1000$ 이기 때문에, 4중 for문을 통한 $O(n^4)$ 의 방법으로는 제한시간인 3초만에 풀 수 없습니다. 그러므로 시간 복잡도를 줄이기 위해서 1번째 리스트와 2번째 리스트, 그리고 3번째 리스트와 4번째 리스트의 모든 합을 구한 다음, 한 쪽을 정렬하여 Binary search를 통해 찾아주면 됩니다. 이 때의 시간 복잡도는 $O(n^2log(n^2))$ 이 됩니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll w[4][1001], p[1000001], q[1000001];
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
ll k, n, t = 0, A;
cin >> k >> n;
for (int i = 0; i < 4; i++)
for (int j = 0; j < n; j++) cin >> w[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
p[t] = w[0][i] + w[1][j], q[t++] = w[2][i] + w[3][j];
sort(q, q + t);
A = p[0] + q[0];
for (int i = 0; i < t; i++)
{
int s = 0, e = t - 1, M;
while (s <= e)
{
M = (s + e) / 2;
ll u = p[i] + q[M];
ll l = abs(k - A), r = abs(k - u);
if (l >= r) A = l == r ? min(A, u) : u;
if (u < k) s = M + 1;
else e = M - 1;
}
}
cout << A << "\n";
}
}