Choosing Column Prefixes

$P_j$를 $1$ 늘릴 때 새로 더해지는 값은 $A_{P_j+1}+B_j$이다. $A$가 내림차순이므로 각 열에서 더 위에 있는 값을 고르지 않고 아래 값을 고르는 일은 최적해에 필요하지 않다. 따라서 전체 $N^2$개의 값 $A_i+B_j$ 중 큰 것 $K$개를 고른 합이 답이다.

어떤 정수 $x$ 이상인 쌍의 개수는 $B$를 정렬한 뒤 각 $A_i$에 대해 이분 탐색하여 $O(N\log N)$에 셀 수 있다. 개수가 $K$ 이상인 가장 큰 $x$를 찾는다. 그 뒤 $x$보다 큰 모든 쌍의 합을 구하고, 부족한 개수만큼 $x$를 더한다. 합은 64비트 정수 범위를 넘을 수 있으므로 128비트 정수를 사용해야 한다.