Cod sursa(job #386360)

Utilizator Addy.Adrian Draghici Addy. Data 24 ianuarie 2010 18:46:54
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdio.h>
#define Nmax 302

int S[Nmax][Nmax], n, m, X, i, j, p, u, t, sum, sol;

int main() {
	
	FILE *f = fopen("teren.in", "r");
	FILE *g = fopen("teren.out", "w");
	
	fscanf(f, "%d %d %d", &n, &m, &X);
	
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++) {
			fscanf(f, "%d", &t);
			S[i][j] = S[i-1][j] + t;
		}
	
	for (i = 1; i < n; i++)
		for (j = i + 1; j <= n; j++) {
			p = 1, sum = 0;
			for (u = 1; u <= m; u++) {
				sum += S[j][u] - S[i-1][u];
				while (p <= u && sum > X) {
					sum -= S[j][p] - S[i-1][p];
					p++;
				}
				
				if (p <= u && (j - i + 1) * (u - p + 1) > sol)
					sol = (j - i + 1) * (u - p + 1);
			}
		}
	
	fprintf(g, "%d", sol);
	
	fclose(f); fclose(g);
	
	return 0;
}