직사각형 2

행 구간의 길이를 $r$, 그 구간의 $A$ 원소 합을 $a$라고 하자. 열 구간의 길이를 $c$, 그 구간의 $B$ 원소 합을 $b$라고 하자.

이 직사각형의 가중치 합은 다음과 같다.

$$\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}(A_i+B_j)=ca+rb$$

따라서 각 길이에 대해 가능한 최대 구간 합만 중요하다. $X_r$를 $A$에서 길이가 정확히 $r$인 연속부분수열 합의 최댓값이라 하고, $Y_c$를 에서 길이가 정확히 인 연속부분수열 합의 최댓값이라고 하자. 정답은 다음 값이다.

$$\max_{1 \le r \le N,\;1 \le c \le M}(cX_r+rY_c)$$

점 $(r,X_r)$들의 위쪽 볼록 껍질과 점 $(c,Y_c)$들의 위쪽 볼록 껍질만 남기면 된다. 어떤 점이 위쪽 볼록 껍질 아래에 있으면, 모든 선형 목적식 $$에 대해 그 점은 최적이 될 수 없기 때문이다.

수열 $A$에 대해 임의의 실수 $\lambda$가 주어졌을 때

$$\max_r(X_r+\lambda r)$$

은 각 원소에 $\lambda$를 더한 수열의 최대 연속부분수열 합과 같다. 따라서 카데인 알고리즘으로 위쪽 볼록 껍질의 한 접점을 구할 수 있다. 이 접점 질의를 이용해 볼록 껍질을 재귀적으로 복원할 수 있다.

두 수열의 볼록 껍질을 모두 구한 뒤에는 한쪽 껍질의 각 점에 대해 다른 쪽 껍질에서 선형 함수의 최댓값을 이분 탐색하거나, 각도 순서로 보며 회전하는 캘리퍼스를 사용하면 된다.

정답의 절댓값은 $64$비트 정수 범위 안에 들어간다.

시간 복잡도는 구현 방식에 따라 $O((N+M)\log^2(N+M))$ 또는 그와 비슷한 수준이다.