codeforces：C. Maximum Subrectangle【前缀和 + 贪心 + 最小子数组和】

分析

两个sigma的求和最终等价于
a的子数组和乘b的子数组和 小于等于 x
对于固定长度的子数组而言，我们都能找出一个和最小的
对于a和b我们都找出指定长度L和最小的子数组和（贪心）
然后一一配对，看看是否面积更大且满足和乘积小于等于x即可

ac code

import sys
import math
from itertools import accumulate
input = sys.stdin.readline

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = int(input())

# (aj1 + ... + aj2) * (bi1 + ... + bi2) <= x
ans = 0
# for a, b; fix length L, the min Sum => greedy
f1 = [math.inf] * (n + 1)
f2 = [math.inf] * (m + 1)
preSum1 = list(accumulate(a, initial = 0))
preSum2 = list(accumulate(b, initial = 0))

# for a
for l in range(1, n + 1):
    for st in range(n - l + 1):
        end = st + l - 1
        f1[l] = min(f1[l], preSum1[end + 1] - preSum1[st])

# for b
for l in range(1, m + 1):
    for st in range(m - l + 1):
        end = st + l - 1
        f2[l] = min(f2[l], preSum2[end + 1] - preSum2[st])

# combine
for l1, v1 in enumerate(f1):
    for l2, v2 in enumerate(f2):
        if l1 * l2 > ans and v1 * v2 <= x:
            ans = l1 * l2

print(ans)

总结

转化为两个子数组的乘积
长度是两个未知数，枚举出来
然后选出当长度固定时最小的和即可
这个用前缀和稍微操作即可