Cod sursa(job #111218)

Utilizator a7893Nae Mihai a7893 Data 28 noiembrie 2007 20:22:25
Problema Teren Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>
#define N 301
int n,m,x,t[N][N],s[N][N],a[N],amax;
void read()
{
	int i,j;
	scanf("%d%d%d",&n,&m,&x);
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			scanf("%d",&t[i][j]);
}
int max(int a,int b)
{
	return a>b?a:b;
}
void solve()
{
	int i,j,p,q,k,st,dr,suma;
	for(p=1;p<=n;++p)
		for(q=1;q<=m;++q)
			s[p][q]=s[p-1][q]+t[p][q];
	for(k=1;k<=m;++k)
		for(i=1;i<=n;++i)
			for(j=1;j<=m;++j)
				a[k]=s[i][k]-s[j-1][k];
	st=1;
	suma=0;
	for(dr=1;dr<=m;++dr)
	{
		suma+=a[dr];
		while(st<=dr&&suma>x)
		{
			suma-=a[st];
			st++;
		}
		if(st<=dr)
			amax=max(amax,(j-i+1)*(dr-st+1));
	}
	printf("%d\n",amax);
}
int main()
{
	freopen("teren.in","r",stdin);
	freopen("teren.out","w",stdout);
	read();
	solve();
	return 0;
}