Cod sursa(job #111733)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 1 decembrie 2007 19:17:13
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <stdio.h>

#define maxn 310
#define max(a,b) (a > b ? a : b)

int n,m,x,sol;
char a[maxn][maxn];
int s[maxn][maxn];
int v[maxn];

int main()
{
	freopen("teren.in","r",stdin);
	freopen("teren.out","w",stdout);

	scanf("%d %d %d ",&n,&m,&x);

	int i,j,k,p,sum;

	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++) scanf("%d ",&a[i][j]);

	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++) s[i][j]=s[i-1][j]+a[i][j];

	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++) 
		{
			for (k=1;k<=m;k++) v[k]=s[j][k]-s[i-1][k];

			sum=0;p=1;

			for (k=1;k<=m;k++)
			{
				sum+=v[k];
				while (sum>x) sum-=v[p++];
				sol=max(sol,(k-p+1)*(j-i+1));
			}
		}

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

	return 0;
}