Cod sursa(job #468165)

Utilizator crushackPopescu Silviu crushack Data 2 iulie 2010 15:08:02
Problema Teren Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#define lung 300

int N,M,X,S[lung+5][lung+5];
int max;

void citire()
{
	int i,j,x;
	freopen("teren.in","r",stdin);
	scanf("%d%d%d",&N,&M,&X);
	for (i=1;i<=N;i++)
	{
		scanf("%d",&x);
		S[1][i]= (i==1) ? x : S[1][i-1]+x;
		for (j=2;j<=M;j++)
		{
			scanf("%d",&x);
			S[i][j]= x+ S[i-1][j] + S[i][j-1] - S[i-1][j-1];
		}
	}
}

int GetQuality(int x1,int y1,int x2,int y2)
{
	return S[x2][y2] - (S[x1-1][y2] + S[x2][y1-1] - S[x1-1][y1-1]);
}

int GetMin(int n,int m)
{
	int i,j,min,x;
	min=-1;
	for (i=n;i<=N;i++)
		for (j=m;j<=M;j++)
		{
			x=GetQuality(i-n,j-m,i,j);
			if (min==-1 || x<min)
				min=x;
		}
	return min;
}

bool bsearchM(int ls,int ld,int x,int n)
{
	int m,xp,r;
	r=-1;
	while (ls<=ld)
	{
		m=(ls+ld)/2;
		xp=GetMin(n,m);
		if (xp<=x)
			r= (m>r) ? m : r,
			ls=m+1;
		else
			ld=m-1;
	}
	max= (n*r>max) ? n*r : max;
	return (r>0);
}

void bsearchN(int ls,int ld)
{
	int m;
	while (ls<=ld)
	{
		m= (ls+ld)/2;
		if (bsearchM(1,M,X,N))
			ls=m+1;
		else
			ld=m-1;
	}
}

void scriere()
{
	freopen("teren.out","w",stdout);
	printf("%d\n",max);
	fclose(stdout);
}

int main()
{
	citire();
	bsearchN(1,N);
	scriere();
	return 0;
}