Cod sursa(job #324795)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 17 iunie 2009 14:18:49
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#define Nmax 305

int a[Nmax][Nmax]; // terenul
long s[Nmax][Nmax],v[Nmax]; // s[i][j]  pe col j si lin<=i sunt x de 1
int n,m,i,j,st,dr,k;
long amax,x,mlg,sum;

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("%d",&a[i][j]);

   for(i=1;i<=n;++i)
     for(j=1;j<=m;++j) 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) v[k] = s[j][k] -s[i-1][k];
         st=1; dr=0; sum=0; mlg=0;
         while(dr<m){
            sum += v[++dr];
         	while(sum > x  && st<=m)
              sum -= v[st++];
            if(st<=dr && dr-st+1 > mlg) mlg=dr-st+1;
         }
         if( (j-i+1)*mlg > amax) amax= (j-i+1)*mlg;
     }

   printf("%ld\n",amax);
   fclose(stdin); fclose(stdout);
   return 0;
}