Cod sursa(job #497507)

Utilizator darrenRares Buhai darren Data 2 noiembrie 2010 18:18:52
Problema Teren Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <algorithm>

using namespace std;

int N, M, X;
bool A[302][302];
int S[302][302];
int result;

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

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

	for (int i1 = 1; i1 <= N; ++i1)
		for (int i2 = i1 + 1; i2 <= N; ++i2)
		{
			int beg = 1, sum = 0;
			for (int j = 1; j <= M; ++j)
			{
				sum += S[i2][j] - S[i1 - 1][j];
				while (sum > X)
					sum -= S[i2][beg] - S[i1][beg], ++beg;
				result = max(result, (j - beg + 1) * (i2 - i1 + 1));
			}
		}

	fout << result;

	fin.close();
	fout.close();
}