Cod sursa(job #496917)

Utilizator andunhillMacarescu Sebastian andunhill Data 31 octombrie 2010 13:50:20
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include<fstream>
using namespace std;
ifstream f("teren.in");
ofstream g("teren.out");
int N,M,X;
int a[301][301];
int b[301];
int i,j,x,i1,i2,maxlen,maxarea;
int main()
{	f>>N>>M>>X;
	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;
}