Cod sursa(job #183443)

Utilizator za_wolfpalianos cristian za_wolf Data 22 aprilie 2008 09:46:45
Problema Teren Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#define NMAX 311
int x[NMAX][NMAX],z[NMAX],y[NMAX][NMAX],i,j,n,m,k,l,a,s,b,q,w,in,sf;
int main()
{
	freopen("teren.in","r",stdin);
	freopen("teren.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			scanf("%d",&x[i][j]);
	for (i=1;i<=m;++i)
		for (j=1;j<=n;++j)
			y[i][j]=y[i][j-1]+x[j][i];

	for (i=1;i<=n;++i)
		for (j=i;j<=n;++j)
		{
			z[0]=0;
			for (l=1;l<=m;++l)
				z[++z[0]]=y[l][j]-y[l][i-1];
			a=0;
			b=-1;
			sf=1;
			in=1;
			while (z[sf]>k&&sf<=m)
				sf++;
			in=sf;
			s=z[sf];

			while (in<=m)
			{
				while (s+z[sf+1]<=k&&sf<m)
				{
					sf++;
					s+=z[sf];
				}
				if (sf-in>b-a)
				{
					a=in;
					b=sf;
				}
				if (in==sf)
					s+=z[++sf];
				while (z[in]==0&&in<=m)
					s-=z[in++];
			}
			if ((j-i+1)*(b-a+1)>w)
				w=(j-i+1)*(b-a+1);

		}

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

	return 0;
}