Pair of Sequences

각 열 $k$를 독립적으로 생각하자.

어떤 두 수열 $P_i,P_j$에 대해 $f(P_i,P_j)$는 어떤 열 $k$에서의 값 $P_{i,k}+P_{j,k}$ 중 최댓값이다. 따라서 열 $k$에서 가능한 가장 큰 합은, 그 열에서 서로 다른 두 수열의 값 중 가장 큰 두 개를 고른 합이다.

각 열마다 가장 큰 값과 두 번째로 큰 값, 그리고 그 값들이 나온 수열 번호를 관리한다. 모든 입력을 읽으면서 각 열의 상위 두 값을 갱신할 수 있다.

입력을 모두 읽은 뒤, 모든 열 $k$에 대해 그 열의 상위 두 값의 합을 확인하고, 가장 큰 합을 만드는 두 수열 번호를 출력하면 된다.

정당성을 보이자. 임의의 두 수열 $P_i,P_j$와 임의의 열 $k$에 대해 $P_{i,k}+P_{j,k}$는 열 에서 서로 다른 두 수열을 골라 만들 수 있는 합이므로, 그 열의 상위 두 값의 합 이하이다. 따라서 어떤 쌍의 값도 우리가 확인한 후보들의 최댓값을 넘을 수 없다. 반대로, 우리가 선택한 열의 상위 두 수열은 실제로 그 합을 만들 수 있으므로 최적값을 달성한다.

시간 복잡도는 $O(NM)$, 메모리 복잡도는 $O(N)$이다.