Cod sursa(job #677841)

Utilizator soriynSorin Rita soriyn Data 10 februarie 2012 18:54:46
Problema Teren Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<stdio.h>
#define maxn 305

int a[maxn],s;
int dp[maxn][maxn];
int n,m,x,k,st,dr;
int max=-1<<30;
void read()
{
    freopen("teren.in","r",stdin);
    int cur;
    scanf("%d%d%d",&n,&m,&x);
    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
         {
             scanf("%d",&cur);
             dp[i][j]=dp[i-1][j]+cur;
         }

}

void solve()
{
    for(int i=1;i<=n;i++)
       for(int j=i;j<=n;j++)
       {
           st=dr=1,s=0;
           int cnt=1;
           for(int dr=1;dr<=m;dr++)
           {
            a[dr]=dp[j-i+1][dr];
            s+=a[dr];
            while(s>x && st<=dr) s-=a[st],st++;
            if(st<=dr && (j-i+1)*(dr-st+1)>max) max=(j-i+1)*(dr-st+1);
           }
       }
}

int main()
{
    read();
    solve();
    freopen("teren.out","w",stdout);

    printf("%d",max);
}