Cod sursa(job #504871)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 29 noiembrie 2010 08:12:11
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
#define inf "teren.in"
#define outf "teren.out"
#define NMax 310
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

short N,M,X;
short T[NMax][NMax], S[NMax][NMax], A[NMax];

void read()
{
	f>>N>>M>>X;
	for(short i=1; i<=N; i++)
		for(short j=1; j<=M; j++) f>>T[i][j]; // O(N*M)
}

inline int max(int a,int b) { return ( a>b ? a : b ); }

void solve()
{
	//S[i][j] - nr de 1 de pe coloana j si liniile <= i
	for(short j=1; j<=M; j++)
		for(short i=1; i<=N; i++) S[i][j] = S[i-1][j] + T[i][j]; // O(N*M)
	
	int max_area = 0;
	for(short i=1; i<=N; i++)
		for(short j=1; j<=N; j++) // O(N^2)
		{
			for(short k=1; k<=M; k++) A[k] = S[j][k] - S[i-1][k]; // O(M)
			
			short st = 1;
			int suma = 0;
			for(short dr=1; dr<=M; dr++) // O(M)
			{
				suma += A[dr];
				while( st<=dr && suma>X ) suma -= A[st], st++;
				if( st<=dr ) max_area = max( max_area, (int)( (j-i+1)*(dr-st+1) ) );
			}
		}
	
	// --> O( N^2 * M )
	g<< max_area;
}

int main()
{
	read(); solve();
	f.close(); g.close();
	return 0;
}