Cod sursa(job #389943)

Utilizator Cristi09Cristi Cristi09 Data 2 februarie 2010 16:02:22
Problema Teren Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<fstream.h>
#include<iostream.h>
#define VMAX 300
int m,n,X,a[VMAX][VMAX],max;
void read()
{   ifstream f("teren.in");
	f>>n>>m>>X;
	int i,j,var;
	for(i=0;i<n;++i)
    for(j=0;j<m;++j)
	{
		f>>var;
		if(i>0)a[i][j]+=a[i-1][j];
		a[i][j]+=var;
	}
	f.close();
}
int suma(int x1,int y1,int x2,int y2)
{
	int i,s=0;
	for(i=y1;i<=y2;++i)
		if(x1>0)s+=a[x2][i]-a[x1-1][i];
		else s+=a[x2][i];
	return s;
}
void search(int x,int y)
{
	int i=x,j=y,var,s=0,jCreste=1;
	while(i>=x)
	{	
		var=(i-x+1)*(j-y+1);
		//if(var<=max)
		//{i=-1;continue;}
		
		s=suma(x,y,i,j);
		if(s<=X&&j<m&&i<n&&var>max)
		{
			max=var;++i;
		}
		else
		{
			if(s<=X&&j<m&&i<n&&jCreste)
				++j;
			else 
			--i;
		}
		if(i==n)
		{--i;++j;}
		if(j>=m)
		{--j;jCreste=0;}
	}
}
int solve()
{
	int i,j;
	for(i=0;i<n;++i)
	for(j=0;j<m;++j)
	if((n-i)*(m-j)>max)
		search(i,j);
	
	return max;
}
int main()
{
	read();
	ofstream g("teren.out");
	g<<solve();
	g.close();
	return 0;
}