Cod sursa(job #496697)

Utilizator ioanabIoana Bica ioanab Data 30 octombrie 2010 12:41:14
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>
using namespace std;

ifstream in("teren.in");
ofstream out("teren.out");

const int N=301;

int a[N][N],sum[N][N];

int main()
{
	int n,m,i,j1,j2,i1,i2,j,s,A,Amax,x;
	in>>n>>m>>x;
	Amax=0;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
		{
			in>>a[i][j];
			sum[i][j]=sum[i][j-1]+a[i][j];
		}
	for(j1=1;j1<=n;++j1)
		for(j2=j1;j2<=m;++j2)
		{
			s=0;
			i2=0;
			for(i1=1;i1<=n;++i1)
			{
				while(i2<=n && s<=x)
				{
					++i2;
					s=s+sum[i2][j2]-sum[i2][j1-1];
				}
				A=(j2-j1+1)*(i2-i1);
				if(A>Amax)
					Amax=A;
				s=s-(sum[i1][j2]-sum[i1][j1-1]);
			}
		}
		
	out<<Amax;
	return 0;
}