Cod sursa(job #191517)

Utilizator wefgefAndrei Grigorean wefgef Data 27 mai 2008 01:20:43
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>

const int MAXN = 305;

int N, M, K;
int A[MAXN][MAXN];
int best;

void ReadData() {
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			scanf("%d", &A[i][j]);
}

inline int max(int a, int b) { return (a > b ? a : b); }

void Solve() {
	for (int i = 1; i <= N; ++i) {
		int v[MAXN] = {};
		for (int j = i; j <= N; ++j) {
			for (int k = 1; k <= M; ++k)
				v[k] += A[j][k];

			int p1 = 0, p2, bad = 0;
			for (p2 = 1; p2 <= M; ++p2) {
				bad += v[p2];
				while (bad > K)
					bad -= v[++p1];
				best = max(best, (j-i+1) * (p2-p1));
			}
		}
	}
}

int main() {
	freopen("teren.in", "r", stdin);
	freopen("teren.out", "w", stdout);

	ReadData();
	Solve();
	printf("%d\n", best);
}