Cod sursa(job #499605)

Utilizator toniobFMI - Barbalau Antonio toniob Data 10 noiembrie 2010 12:21:52
Problema Teren Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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 = 0, suma = 0; sus <= n; ++sus) {
				while (jos <= n && suma <= x) {
					++jos;
					suma += v[jos][j] - v[jos][i - 1];
				}
				
				arie = (j - i + 1) * (jos - sus);
				
				if (arie > ariemax) {
					ariemax = arie;
				}
				
				suma -= v[sus][j] - v[sus][i - 1];
			}
		}
	}
}

void afisare () {
	out << ariemax << '\n';
}

int main () {
	citire ();
	
	exe ();
	
	afisare ();
	
	return 0;
}