Cod sursa(job #497537)

Utilizator toniobFMI - Barbalau Antonio toniob Data 2 noiembrie 2010 20:02:32
Problema Teren Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
using namespace std;

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

const int N = 1 << 9;
const int M = 1 << 9;
int n, m, x, v[N][M], arie, ariemax;

void sume_partiale () {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			v[i][j] += v[i][j - 1];
		}
	}
}

void citire () {
	in >> n >> m >> x;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			in >> v[i][j];
		}
	}
}

void exe () {
	sume_partiale ();

	for (int i = 1; i <= m; ++i) {
		for (int j = i; j <= m; ++j) {
			for (int sus = 1, jos = 1, suma = 0; sus <= n; ++sus) {
				for (; jos < n && suma <= x; ) {
				    ++j;
					suma += v[jos][j] - v[jos][i - 1];
					arie = (j - i + 1) * (jos - sus + 1);
				}

				if (suma <= x && arie > ariemax) {
					ariemax = arie;
				}

				suma -= v[sus][j] - v[sus][i - 1];
			}
		}
	}
}

void afisare () {
	out << ariemax;
}

int main () {
	citire ();

	exe ();

	afisare ();

	return 0;
}