Cod sursa(job #1096774)

Utilizator andreiiiiPopa Andrei andreiiii Data 2 februarie 2014 16:27:40
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <algorithm>
#include <cstdio>

using namespace std;

const int N=305;

int a[N][N], b[N][N];

int main()
{
    freopen("teren.in", "r", stdin);
    freopen("teren.out", "w", stdout);
    int n, m, i, j, i1, i2, s, k, sol=0;
    scanf("%d%d%d", &n, &m, &k);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%d", &a[i][j]);
            b[i][j]=b[i-1][j]+a[i][j];
        }
    }
    for(i1=1;i1<=n;i1++)
    {
        for(i2=i1;i2<=n;i2++)
        {
            j=1;
            s=0;
            for(i=1;i<=m;i++)
            {
                s+=b[i2][i]-b[i1-1][i];
                for(;j<=i&&s>k;j++)
                {
                    s-=b[i2][j]-b[i1-1][j];
                }
                sol=max(sol, (i2-i1+1)*(i-j+1));
            }
        }
    }
    printf("%d", sol);
}