Cod sursa(job #124333)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 18 ianuarie 2008 20:59:54
Problema Teren Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>

long n,m,i,j,k,x,a[302][302];
long s[302][302],b[302],st,dr,arie,amax,suma;

int main(){
    freopen("teren.in","r",stdin);
    freopen("teren.out","w",stdout);
    
    scanf("%ld %ld %ld",&n,&m,&x);
    
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            scanf("%ld",&a[i][j]);
        }
    for (j=1;j<=m;j++)
        for (i=1;i<=n;i++)
            s[i][j]=s[i-1][j]+a[i][j];
            
    for (i=1;i<=n;i++)
        for (j=i;j<=n;j++){
            for (k=1;k<=m;k++)b[k]=s[j][k]-s[i-1][k];
            st=1;
            arie=(j-i+1);
            if (arie>amax)amax=arie;
            suma=b[1];
            for (dr=2;dr<=m;dr++){
                suma+=b[dr];
                while (suma>x&&st<m){
                      suma-=b[st];
                      st++;
                }
                arie=(dr-st+1)*(j-i+1);
                if (arie>amax)amax=arie;
            }
        }
        
    printf("%ld\n",amax);
    
    return 0;
}