Cod sursa(job #733506)

Utilizator danalex97Dan H Alexandru danalex97 Data 12 aprilie 2012 12:53:37
Problema Teren Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
using namespace std;

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

void CloseFiles()
{
	F.close();
	G.close();
}

#define Dmax 311

int N,M,X;
int A[Dmax][Dmax];
int S[Dmax][Dmax];
int St,Dr,Sum,Lmax,Deque[Dmax];

int main(void)
{
	F>>N>>M>>X;
	
	for (int i=1;i<=N;++i)
		for (int j=1;j<=M;++j)
			F>>A[i][j],
			S[i][j]=S[i-1][j]+A[i][j];
	
	int i,jj;
	Lmax=0;
	
	for (i=1;i<=N;++i)
		for (jj=i;jj<=N;++jj)
		{
			St=1,Dr=1;
			
			for (int ii=1;ii<=M;++ii)
				Deque[ii]=S[jj][ii]-S[i-1][ii];
			Deque[M+1]=X+1;
			
			Sum+=Deque[1];
			while ( Sum > X )
				++St,++Dr,Sum=Deque[St];
			
			while ( Dr <= M+1 )
			{
				++Dr,Sum+=Deque[Dr];
				
				if ( Sum > X ) Lmax=max(Lmax, (Dr-St) * (jj-i+1) );
				
				while ( Sum > X )
					++St,Sum-=Deque[St];
				
				if ( St > Dr )
				{
					++Dr;
					Sum+=Deque[Dr];
					while ( Sum > X )
						++St,++Dr,Sum=Deque[St];
				}
			}
		}
	
	G<<Lmax<<'\n';
	
	CloseFiles();
}