Cod sursa(job #497502)

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

using namespace std;

int N, M, X;
int 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)
		{
			fin >> A[i][j];
			S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j];
		}

	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			for (int k = 0; k < j; ++k)
			{
				// S[i][j] - S[i][k - 1] - S[aux][j] + S[aux][k - 1]
				int con = S[i][j] - S[i][k];

				int step, aux;
				for (step = 1; (step << 1) <= i + 1; step <<= 1);
				for (int l = i + 1; step; step >>= 1)
					if (l - step >= 0 && con - S[l - step][j] + S[l - step][k] <= X)
						l -= step, aux = l;

				result = max(result, (j - k) * (i - aux));
			}

	fout << result;

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