Cod sursa(job #497217)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 1 noiembrie 2010 21:08:28
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<stdio.h>

#define maxim(a,b) (a>b ? a : b)

int n,m,lim;
int p[304],sm;
int d[304][304];

int main ()
{
    int i,j,k,a,st=0,sol=0;
    freopen("teren.in","r",stdin);
    freopen("teren.out","w",stdout);
    scanf("%d%d%d",&n,&m,&lim);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            scanf("%d",&a);
            d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a;
        }
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
        {
            st=1;sol=0;
            for(k=1;k<=m;k++)
            {
                p[k]=d[i][k]-d[i][k-1]-d[i-j][k]+d[i-j][k-1];
                sol+=p[k];
                while(st<=k && sol>lim)
                {
                    sol-=p[st];
                    st++;
                }
                sm=maxim(sm,(k-st+1)*j);
            }
        }
    printf("%d\n",sm);
    return 0;
}