직사각형 1

직사각형 영역의 행 범위를 $x_1$부터 $x_2$까지, 열 범위를 $y_1$부터 $y_2$까지 골랐다고 하자.

이때 가중치 합은 다음과 같다.

$$\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2} A_iB_j = \left(\sum_{i=x_1}^{x_2} A_i\right) \left(\sum_{j=y_1}^{y_2} B_j\right)$$

따라서 문제는 $A$의 연속부분수열 합 하나와 $B$의 연속부분수열 합 하나를 골라 두 값의 곱을 최대로 만드는 문제와 같다.

각 수열에 대해 필요한 값은 연속부분수열 합의 최솟값과 최댓값이다. $A$의 연속부분수열 합의 최솟값과 최댓값을 각각 $\mathrm{minA}, \mathrm{maxA}$라 하고, $B$에 대해서도 $\mathrm{minB}, \mathrm{maxB}$라 하자.

정답은 다음 네 값 중 최댓값이다.

$$\mathrm{minA}\mathrm{minB},\quad \mathrm{minA}\mathrm{maxB},\quad \mathrm{maxA}\mathrm{minB},\quad \mathrm{maxA}\mathrm{maxB}$$

연속부분수열은 비어 있을 수 없다는 점에 주의해야 한다.

연속부분수열 합의 최댓값과 최솟값은 카데인 알고리즘으로 각각 $O(N)$, $O(M)$에 구할 수 있다. 정답의 절댓값은 최대 $4 \times 10^{18}$이므로 $64$비트 정수를 사용해야 한다.

전체 시간 복잡도는 $O(N+M)$이다.