Cod sursa(job #492846)

Utilizator ChallengeMurtaza Alexandru Challenge Data 16 octombrie 2010 07:37:31
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <queue>

//#define DEBUG

using namespace std;

const char InFile[]="teren.in";
const char OutFile[]="teren.out";
const int MaxN=305;

ifstream fin(InFile);
ofstream fout(OutFile);

int n,m,t,psum[MaxN][MaxN],sol,l,x,sum;

int main()
{
	fin>>n>>m>>x;
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=m;++j)
		{
			fin>>t;
			psum[i][j]=t+psum[i-1][j];
		}
	}
	fin.close();

#ifdef DEBUG
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=m;++j)
		{
			fout<<psum[i][j]<<" ";
		}
		fout<<"\n";
	}
	fout<<"\n\n";
#endif

	for(register int i=1;i<=n;++i)
	{
		for(register int j=i;j<=n;++j)
		{
			queue<int> q;
			l=0;
			sum=0;
			for(register int k=1;k<=m;++k)
			{
				++l;
				int lat=psum[j][k]-psum[i-1][k];
				sum+=lat;
				q.push(lat);
				while(sum>x)
				{
					sum-=q.front();
					q.pop();
					--l;
				}
				if(l*(j-i+1)>sol)
				{
					sol=l*(j-i+1);
				}
			}
		}
	}

	fout<<sol;
	fout.close();
	return 0;
}