Cod sursa(job #110811)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 27 noiembrie 2007 20:12:48
Problema Teren Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 304;

int N, M, K, Rez, A[NMAX][NMAX];

void read(void) {
	FILE *fin = fopen("teren.in", "rt");
	int i, j;

	fscanf(fin, " %d %d %d", &N, &M, &K);

	for (i = 1; i <= N; ++i)
		for (j = 1; j <= M; ++j)
			fscanf(fin, " %d", A[i] + j),
			A[i][j] += A[i - 1][j];

	fclose(fin);
}

void solve(void) {
	int i, j, k;
	int T[NMAX], ind[NMAX];

	for (i = 1; i <= N; ++i) {

		for (j = 1; j <= i; ++j)
			T[j] = ind[j] = 0;

		for (j = 1; j <= M; ++j) {
			
			for (k = 1; k < i; ++k) {
				T[k] += A[i][j] - A[k - 1][j];

				while (T[k] > K) {
					T[k] -= A[i][ ind[k] ] - A[k - 1][ ind[k] ];
					++ind[k];
				}

//				printf("%d %d %d (%d) => %d\n", i, j, k, ind[k], (i - k + 1) * (j - ind[k]));

				Rez = max(Rez, (i - k + 1) * (j - ind[k]));
			}

		}
	}
}

void write(void) {
	FILE *fout = fopen("teren.out", "wt");

	fprintf(fout, "%d\n", Rez);

	fclose(fout);
}

int main(void) {
	
	read();

	solve();

	write();

	return 0;
}