Cod sursa(job #123435)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 15 ianuarie 2008 22:18:03
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
//teren
#include<stdio.h>
FILE*fin=fopen("teren.in","r");
FILE*fout=fopen("teren.out","w");
int main()
{
  short a[301][301],s[301][301];
  long nmax=0,i,j,c,ci,nx,n,m,x;
  fscanf(fin,"%ld" "%ld" "%ld",&n,&m,&x);
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      fscanf(fin,"%d",&a[i][j]);
  fclose(fin);
  for(j=1;j<=m;j++)
  {
    s[0][j]=0;
    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++)
    {
      ci=1;nx=0;
      for(c=1;c<=m;c++)
      {
	nx+=(s[j][c]-s[i-1][c]);
	while(nx>x&&c>=ci){nx-=(s[j][ci]-s[i-1][ci]);ci++;}
	if((c-ci+1)*(j-i+1)>nmax&&c>=ci) nmax=(c-ci+1)*(j-i+1);
      }
    }
  fprintf(fout,"%ld",nmax);
  fclose(fout);
  return 0;
}