Cod sursa(job #111741)

Utilizator savimSerban Andrei Stan savim Data 1 decembrie 2007 19:42:05
Problema Teren Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<stdio.h>
int i,j,k,n,m,x,supmax=0,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];
	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;
		    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)
			      {
			         sup=(q-p+1)*(j-i+1);
			         if (sup>supmax) supmax=sup;
			      }
		 }
		}


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