Cod sursa(job #206239)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 5 septembrie 2008 14:19:08
Problema Teren Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#include <math.h>

long n, m, x, i, j, v[301][301], a[301][301], def, ter, max, capst, capdr;

int main() {
	freopen("teren.in", "r", stdin);
	freopen("teren.out", "w", stdout);
	scanf("%ld %ld %ld", &n, &m, &x);
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= m; ++j) {
			scanf("%ld", &v[i][j]);
		}
	}
	for (i = 1; i <= m; ++i) {
		for (j = 1; j <= n; ++j) {
			if (v[j][i] == 1) {
				a[j][i] = a[j - 1][i] + 1;
			} else {
				a[j][i] = a[j - 1][i];
			}
		}
	}
	for (i = 1; i <= n; ++i) {
		for (j = i; j <= n; ++j) {
			capst = 1;
			capdr = 1;
			def = a[j][1] ;
			ter = j - i + 1;
			while (capdr != m) {
				if (def + a[j][capdr] - a[i - 1][capdr] <= x) {
					++capdr;
					def += (a[j][capdr] - a[i - 1][capdr]);
					ter += j - i + 1;
				} else {
					++capst;
					def -= (a[j][capst] - a[i - 1][capst]);
					ter -= (j - i + 1);
				}
				if (max < ter && def <= x) {
					max = ter;
				}
			}
		}
	}
	printf("%ld\n", max);
	return 0;
}