Cod sursa(job #102832)

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

using namespace std;

#define nmax 302
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define mp make_pair
#define pb push_back
#define f first
#define sz size()
#define s second

int n,A[nmax][nmax],sol,m,X,B[nmax],cnt=100000000;
pair <int,int> P[nmax*nmax];

int sum(int i,int j,int x,int y)
{
	int aux=A[x][y];
	if(i)
		aux-=A[i-1][y];
	if(j)
		aux-=A[x][j-1];
	if(i&&j)
		aux+=A[i-1][j-1];
	return aux;
}

int main()
{
	int i,j,k,x,y,xx;
	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];
		if(i)
			A[i][j]+=A[i-1][j];
		if(i&&j)
			A[i][j]-=A[i-1][j-1];
	}
	for(;;);
	FOR(i,0,n) FOR(j,0,m)
		P[i*m+j]=mp(i,j);
	random_shuffle(P,P+n*m);
	FOR(k,0,n*m)
	{
		x=P[k].f, y=P[k].s;
		for(i=n-1;i>=x;--i)
		{
			for(j=m-1;j>=y;--j)
			{
				if(sol>=(xx=(i-x+1)*(j-y+1)))
					break;
				if(sum(x,y,i,j)<=X)
				{
					sol=xx;
					break;
				}
				cnt--;
			}
		}
		if(cnt<0)
			break;
	}

	printf("%d\n",sol);
	return 0;
}