Cod sursa(job #375065)

Utilizator Mishu91Andrei Misarca Mishu91 Data 19 decembrie 2009 12:46:11
Problema Teren Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>

using namespace std;

#define MAX_N 305

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

int N, M, X, A[MAX_N][MAX_N], S[MAX_N], Sol;

void citire()
{
	fin >> N >> M >> X;

	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
		{
			fin >> A[i][j];
			A[i][j] += A[i-1][j];
		}
}

void solve()
{
	for(int i = 1; i <= N; ++i)
		for(int j = i; j <= N; ++j)
		{
			for(int k = 1; k <= M; ++k)
				S[k] = A[j][k] - A[i-1][k];

			int sum = 0;
			for(int st = 1, dr = 1; st <= N; ++st)
			{
				if(S[st] > X)
				{
					sum = 0;
					dr = st+1;
					continue;
				}

				while(sum > X)
					sum -= S[dr++];

				if((st-dr+1)*(j-i+1) > Sol)
					Sol = (st-dr+1)*(j-i+1);
			}
		}

	fout << Sol << "\n";
}

int main()
{
	citire();
	solve();
}