Cod sursa(job #183439)

Utilizator za_wolfpalianos cristian za_wolf Data 22 aprilie 2008 09:40:57
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 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]*/y[sf][j]-y[sf][i-1]>k&&sf<=m)
				sf++;
			in=sf;
			s=y[sf][j]-y[sf][i-1]/*z[sf]*/;

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

			}
			if ((j-i+1)*(b-a+1)>w)
				w=(j-i+1)*(b-a+1);

		}

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

	return 0;
}