Cod sursa(job #677753)

Utilizator Mitza444Vidrean Mihai Mitza444 Data 10 februarie 2012 16:46:03
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <cstdio>
#include <queue>
using namespace std;
int n,m,x,A,S[301][301];
int i,j,rez;
int l1,l2,suma,nre,a,v;
queue <int> Q;
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);
			S[i][j]=S[i-1][j]+A;
		}
	rez=0;
	for (l1=1;l1<=n;l1++)
		for (l2=l1;l2<=n;l2++)
		{
			while (!Q.empty())
				Q.pop();
			nre=suma=0;
			for (i=1;i<=m;i++)
			{
				v=S[l2][i]-S[l1-1][i];
				Q.push(v);
				nre++;
				suma=suma+v;
				while (suma>x)
				{
					a=Q.front();
					Q.pop();
					suma=suma-a;
					nre--;
				}
				if (nre*(l2-l1+1)>rez)
					rez=nre*(l2-l1+1);
			}
		}
	printf("%d\n",rez);
	return 0;
}