Cod sursa(job #478885)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 20 august 2010 23:12:35
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>

#define file_in "teren.in"
#define file_out "teren.out"

int n,m,x;
int a[333][333];
int s[333];

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d %d", &n, &m,&x);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
		{
			scanf("%d", &a[i][j]);
			a[i][j]+=a[i-1][j];
		}
}

void solve()
{
	int i,j,k,st,dr,suma,max=0;
	for (i=1;i<=n;++i) 
		 for (j=1;j<=n;++j)
		 {
			 for (k=1;k<=m;++k)
				  s[k]=a[j][k]-a[i-1][k];
			 st=1;
			 suma=0;
			 for (dr=1;dr<=m;++dr)
			 {
				 suma+=s[dr];
				 while(st<=dr && suma>x)
				 {	 suma-=s[st];
				     st++;
				 }
				 if (st<=dr && (j-i+1)*(dr-st+1)>max)
					 max=(dr-st+1)*(j-i+1);
			 }
		 }
	printf("%d\n", max);
}	
					 
			 

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}