Cod sursa(job #390616)

Utilizator Cristi09Cristi Cristi09 Data 4 februarie 2010 10:29:41
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<fstream.h>
#include<string.h>
#define VMAX 300
int m,n,X,maxim,apel=1,mat[VMAX][VMAX],lin[VMAX][VMAX];
char buf[810];
void read()
{
//	FILE*f=fopen("teren.in","r");
//	fscanf(f,"%d %d %d",&n,&m,&X);
	ifstream f("teren.in");
	f>>n>>m>>X;
	int i,j;
	int v[VMAX];
//	fgets(buf,10,f);
	f.getline(buf,10);
	int siz,ct;
	for(i=0;i<n;++i)
	{
		//fgets(buf,810,f);
		f.getline(buf,810);
		siz=strlen(buf);
		for(j=0,ct=0;j<siz;j+=2,++ct)
		{
			if(i==0)v[ct]=0;
			v[ct]+=buf[j]-48;

			lin[i][ct]=v[ct];
			if(ct>0)lin[i][ct]+=lin[i][ct-1];
		}
	}
	f.close();
}
int suma(int x1,int y1,int x2,int y2)
{
	int i=0,s;
	s=lin[x2][y2];
	if(y1>0){s-=lin[x2][y1-1];i=1;}
	if(x1>0)
	{
		if(i)s-=(lin[x1-1][y2]-lin[x1-1][y1-1]);
		else s-=lin[x1-1][y2];
	}
	return s;
}
void search(int x,int y)
{
	int i=x,j=y,var,s=0;
	while(i>=x)
	{
		var=(i-x+1)*(j-y+1);
		s=suma(x,y,i,j);
		if(mat[i][j]!=apel)mat[i][j]=apel;
		else s=X+1;
		if(s<=X&&j<m&&i<n)
		{
			if(var>maxim)maxim=var;
			if(mat[i+1][j]!=apel)++i;
			else ++j;
		}
		else
		{
			--i;
			if((i-x+1)*(m-y)<=maxim)
			return;
			while(mat[i][j]==apel||(i-x+1)*(j-y+1)<=maxim)
			{
				mat[i][j]=apel;++j;
				if(j>=m){--i;j=y;}
				if(i<x||(i-x+1)*(m-y)<=maxim)return;
			}
		}
		if(i==n)
		{--i;++j;}
		if(j>=m)
		{--j;}
	}
}
int solve()
{
	int i,j,var;
	maxim=0;
	for(i=0;i<n;++i)
	for(j=0;j<m;++j)
	if((n-i)*(m-j)>maxim){search(i,j);++apel;}

	return maxim;
}
int main()
{
	read();
	//FILE*g=fopen("teren.out","w");
	//fprintf(g,"%d",solve());
	ofstream g("teren.out");
	g<<solve();
	g.close();
	return 0;
}