Cod sursa(job #496379)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 28 octombrie 2010 18:25:22
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<cstdio>
int n,m,x,q,tot,dr,st,poz,v[305],a[305][305],s[305][305];
void read()
{
	freopen("teren.in","r",stdin);
	freopen("teren.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]);
}
void init()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			s[i][j]=s[i][j-1]+a[i][j];
}
void start(int c1,int c2)
{
	while(tot+s[poz][c2]-s[poz][c1-1]<=x && poz<=n)
		tot+=s[poz][c2]-s[poz][c1-1], v[++dr]=poz, poz++;
}
void solve()
{
	int sact=0,max=-1;
	for(int j1=1;j1<=m;j1++)
		for(int j2=j1+1;j2<=m;j2++)
		{
			dr=st=0;
			tot=0;
			poz=1;
			start(j1,j2);
			st=1;
			sact=(j2-j1+1)*(dr-st+1);
			if(sact>max)
				max=sact;
			for(int i=poz;i<=n;i++)
			{
				tot+=s[i][j2]-s[i][j1-1];
				while(tot>x)
				{
					tot-=(s[v[st]][j2]-s[v[st]][j1-1]);
					st++;
				}
				v[++dr]=i;
				sact=(j2-j1+1)*(dr-st+1);
				if(sact>max)
					max=sact;
			}
		}
	printf("%d",max);
}
int main()
{
	read();
	init();
	solve();
	return 0;
}