Cod sursa(job #499596)

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

void afisare () {
	out << ariemax;
}

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