蒟蒻WA求助
查看原帖
蒟蒻WA求助
342798
Desert_Lycoris楼主2020/8/29 15:34
#include<bits/stdc++.h>
using namespace std;
const int N = 300;
int n, m, rac[N][N], sum[N][N], pos[N], ans = INT_MIN;
struct node
{
    int val, pos;
}a[N];
bool comp(node x, node y)
{
    return x.val < y.val;
}
void prepare(int sj, int xj)
{
    memset(a, 0, sizeof(a));
    pos[0] = 0;
    for(int i = 1; i <= m; i++)
    {
        a[i].pos = i;
        for(int j = sj; j <= xj; j++)
        {
            a[i].val += sum[j][i];
        }
    }
    sort(a + 1, a + m + 1, comp);
    pos[1] = a[1].pos;
    for(int i = 2; i <= m; i++)
    {
        pos[i] = min(a[i].pos, pos[i-1]);
    }//前缀最小值
}
int main()
{
    cin >> n >> m;
    memset(sum, 0, sizeof(sum));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> rac[i][j];
            sum[i][j] = sum[i][j - 1] + rac[i][j];
        }
    }
    for(int x1 = 1; x1 <= n; x1++)
    {
        for(int x2 = x1; x2 <= n; x2++)
        {
            prepare(x1, x2);
            for(int i = m; i >= 1; i--)
            {
                if(a[i].val >= 0)
                {
                    ans = max(ans, (a[i].pos - pos[i-1] + 1) * (x2 - x1 + 1));
                }
            }
        }
    }
    cout << ans;
    return 0;
}

样例过了

2020/8/29 15:34
加载中...