Cod sursa(job #496914)

Utilizator andunhillMacarescu Sebastian andunhill Data 31 octombrie 2010 13:48:26
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<fstream>
using namespace std;
ifstream f("teren.in");
ofstream g("teren.out");
int main()
{	int N,M,X;
	int i,j,x,i1,i2,maxlen,maxarea;
	int b[301];
	int a[301][301];
	f>>N>>M>>X;
	for(i=1;i<=M;i++) a[0][i]=0;
	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++)
		{	f>>x;
			a[i][j]=a[i-1][j]+x;
		}
	maxarea=-9999;
	for(i1=1;i1<=N;i1++)
		for(i2=i1;i2<=N;i2++)
		{	maxlen=-99999;
			for(i=j=1;i<=M;i++)
			{	b[i]=b[i-1]+a[i2][i]-a[i1-1][i];
				while(b[i]-b[j-1]>X) j++;
				maxlen=max(maxlen,i-j+1);
			}
			maxarea=max(maxarea,(i2-i1+1)*maxlen);
		}
	g<<maxarea;
	f.close();
	g.close();
	return 0;
}