Cod sursa(job #111355)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 29 noiembrie 2007 17:04:48
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
/* Ivan Nicolae - Bucuresti */
/* Infoarena - Teren */
#include <stdio.h>

#define NMAX 301
#define _fin  "teren.in"
#define _fout "teren.out"

int i,j,k,n,m,x,A[NMAX][NMAX],B[NMAX][NMAX],V[NMAX];

int main()
{
 freopen(_fin,"r",stdin);
 freopen(_fout,"w",stdout);

 scanf("%d%d%d",&n,&m,&x);
 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    scanf("%d",&A[i][j]);

 for (j=1;j<=m;j++)
 for (i=1;i<=n;i++)
    B[i][j]=B[i-1][j]+A[i][j];

 int ariemax=0;
 for (i=1;i<=n-1;i++)
 for (j=i+1;j<=n;j++)
    {
     for (k=1;k<=m;k++)
        V[k]=B[j][k]-B[i-1][k];

     int l=1,r=1,suma=0;
     
     for (r=1;r<=m;r++)
        {
         suma+=V[r];
         while (suma>x && l<r)
              suma-=V[l++];
         if ((j-i+1)*(r-l+1) > ariemax && suma<=x)
           ariemax=(j-i+1)*(r-l+1);
        }
    }

 printf("%d\n",ariemax);

 fclose(stdin);
 fclose(stdout);
 return 0;
}