Cod sursa(job #112442)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 5 decembrie 2007 15:09:06
Problema Teren Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#include <math.h>

long n, i, j, k, a[101][101], s[101][101], sum_max, sum_cur, h, v[101], nr, sum, fr, poz1, poz2, x, m, maxim;

int main() {
	#ifndef ONLINE_JUDGE
	freopen("teren.in", "r", stdin);
	freopen("teren.out", "w", stdout);
	#endif
	scanf("%ld%ld%ld", &n, &m, &x);
	for (i = 1;i <= n; ++i) {
		for (j = 1;j <= m; ++j) {
			scanf("%ld", &a[i][j]);
		}
	}
	for (i = 1; i <= m; ++i) {
		sum = 0;
		for (j = 1; j <= n; ++j) {
			sum += a[j][i];
			s[j][i] = sum;
		}
	}
	for (i = 1;i <= n; ++i) {
		for (j = i ; j <= n; ++j) {
			for (k = 1; k <= m; ++k) {
				v[k] = s[j][k] - s[i - 1][k];
			}
			sum_cur = 0;
			poz1 = 1;
			for (k = 1; k <= m; ++k) {
				if (sum_cur < 0) {
					sum_cur = v[k];
					poz1 = k;
				} else {
				sum_cur = sum_cur + v[k];
				}
				if (sum_cur > x) {
					for (h = 1;h <= m; ++h) {
						sum_cur = sum_cur - v[h];
						if (sum_cur <= x) {
							poz1 = h + 1;
							break;
						}
					}
				}
				if ((sum_cur > sum_max && sum_cur <= x) || ((j - i + 1) * (k - poz1 + 1) > maxim && sum_cur <= x)) {
					sum_max = sum_cur;
					fr = j - i + 1;
					poz2 = k;					
					maxim = fr * (poz2 - poz1 + 1);
				}
			}
		}
	}
	printf("%ld", maxim);
	return 0;
}