CF1060C Maximum Subrectangle

思路：

不难发现，对矩阵中的数字求和实际上是先分别对a，b两个数列中对应子段的元素求和再相乘。题目是要求在和不超过给定值的情况下使选出的矩阵面积最大。我们反其道而行之，考虑在子段长度一定的情况下，和最小是多少。具体来说，首先分别计算a的长度为1，2，...，n的子段中的和的最小值，记为min1[i](i = 1, 2, ..., n)。对b做类似处理得到min2[i](i = 1, 2, ..., m)。然后枚举min1和min2的所有组合即可得出答案。

实现：

 #include <iostream>

 #include <cstring>

 using namespace std;

 typedef long long ll;

 const int MAXN = ;

 const int MAXM = ;

 int a[MAXN], b[MAXM], n, m;

 ll sum1[MAXN], sum2[MAXM], min1[MAXN], min2[MAXM], x;

 int main()

 {

     while (cin >> n >> m)

     {

         memset(sum1, , sizeof sum1);

         memset(sum2, , sizeof sum2);

         memset(min1, 0x3f, sizeof min1);

         memset(min2, 0x3f, sizeof min2);

         for (int i = ; i <= n; i++)

         {

             cin >> a[i];

             sum1[i] = sum1[i - ] + a[i];

         }

         for (int i = ; i <= m; i++)

         {

             cin >> b[i];

             sum2[i] = sum2[i - ] + b[i];

         }

         cin >> x;

         for (int i = ; i <= n; i++)

         {

             for (int j = ; j < n - i + ; j++)

             {

                 min1[i] = min(min1[i], sum1[i + j] - sum1[j]);

             }

         }

         for (int i = ; i <= m; i++)

         {

             for (int j = ; j < m - i + ; j++)

             {

                 min2[i] = min(min2[i], sum2[i + j] - sum2[j]);

             }

         }

         int ans = ;

         for (int i = ; i <= n; i++)

         {

             for (int j = ; j <= m; j++)

             {

                 if (min1[i] <= x && x / min1[i] >= min2[j])

                 {

                     ans = max(ans, i * j);

                 }

             }

         }

         cout << ans << endl;

     }

     return ;

 }