Cod sursa(job #111575)

Utilizator savimSerban Andrei Stan savim Data 30 noiembrie 2007 19:08:03
Problema Teren Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<stdio.h>
int i,j,k,n,m,x,supmax=0,max=-1,p,q,sup;
int a[301][301],s[301][301];
int v[301];
int main()
{
	freopen("teren.in","r",stdin);
	freopen("teren.out","w",stdout);
	scanf("%d%d%d",&n,&m,&x);
	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];
	max=0;supmax=0;
	for (i=1; i<=n; i++)
		for (j=n; j>=i; j--)
		{
		 for (k=1; k<=m; k++)
			v[k]=s[j][k]-s[i-1][k];

		 p=1;
		 q=0;
		 max=-1;
		 int sup=0;
		 int s=0;
		 while (q<m)
		 {
			q++;
			s=s+v[q];
			if (s>x)
			{
				s=0;
				p++;
				q=p-1;
			}
			else
			if ((q-p+1)*(j-i+1)>sup)
			{
				max=s;
				sup=(q-p+1)*(j-i+1);
				if (sup>supmax) supmax=sup;
				sup=0;
			}
		 }
		}


	printf("%d",supmax);
	return 0;
}