Cod sursa(job #221826)

Utilizator savimSerban Andrei Stan savim Data 18 noiembrie 2008 11:54:15
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>

#define MAX_N 310

int n, m, lim, i, j, k, val, p, q, suma;
int a[MAX_N][MAX_N], sum[MAX_N][MAX_N];

void cit() {
	freopen("teren.in", "r", stdin);
	freopen("teren.out", "w", stdout);
	
	scanf("%d %d %d", &n, &m, &lim);
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
			sum[i][j] = sum[i - 1][j] + a[i][j];
		}
}

void solve() {
	for (i = 1; i <= n; i++)
		for (j = i; j <= n; j++) {
			p = 1; suma = 0;
			for (k = 1; k <= m; k++) {
				suma += sum[j][k] - sum[i - 1][k];;
				
				while (suma > lim) {
					suma -= sum[j][p] - sum[i - 1][p];
					p++;
				}
				
				if ((k - p + 1) * (j - i + 1) > val)
					val = (k - p + 1) * (j - i + 1);
			}
		}
	
	printf("%d\n",val);
}

int main() {
	cit();
	solve();
	
	return 0;
}