Cod sursa(job #102811)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 14 noiembrie 2007 18:41:27
Problema Teren Scor Ascuns
Compilator cpp Status done
Runda Marime 0.82 kb
#include <stdio.h>
#include <assert.h>

#define nmax 302
#define FOR(i,s,d) for(i=(s);i<(d);++i)

int n,A[nmax][nmax],sol,m,X,B[nmax];

void doit(int l)
{
	int aux=0,i,j=0;
	FOR(i,0,n)
	{
		if(j<i)
			j=i,aux=0;
		for(;j<n&&aux+B[j]<=X;aux+=B[j++]);
		if((j-i)*l>sol)
			sol=(j-i)*l;
		aux-=B[i];
	}
}

int main()
{
	int i,j,k;
	assert(freopen("teren.in","r",stdin));
	freopen("teren.out","w",stdout);
	assert(scanf("%d %d %d",&n,&m,&X)==3);
	assert(n<=300);
	assert(n>=1);
	assert(m<=300);
	assert(m>=1);
	assert(X<=n*m);
	assert(X>=0);
	FOR(i,0,n) FOR(j,0,m)
	{
		assert(scanf("%d",&A[i][j])==1);
		assert(A[i][j]<=1);
		assert(A[i][j]>=0);
		if(j)
			A[i][j]+=A[i][j-1];
	}
	FOR(i,0,m) for(j=m-1;j>=i;--j)
	{
		if((j-i+1)*n<sol)
			break;
		FOR(k,0,n)
			B[k]=A[k][j]-(i?A[k][i-1]:0);
		doit(j-i+1);
	}
	printf("%d\n",sol);
	return 0;
}