Cod sursa(job #812834)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 14 noiembrie 2012 16:07:41
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>
#include <queue>
using namespace std;
int n,m,x,A,S[301][301],i,j,rez,l1,l2,suma,nre,a,v;
char ch[605];
queue <int> Q;
int main()
{
	freopen("teren.in","r",stdin);
	freopen("teren.out","w",stdout);
	scanf("%d%d%d\n",&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;}*/
	 for (i=1;i<=n;++i)
        S[i][0]=0;
	for (i=1;i<=n;i++)
    {
        fgets(ch,605,stdin);
        for (j=1;j<=m;j++)
            S[i][j]=S[i-1][j]+(ch[j*2-2]-'0');
    }
	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;
}