Cod sursa(job #184301)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 23 aprilie 2008 14:09:29
Problema Teren Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>

const int N_MAX = 310;

int a[N_MAX][N_MAX], sum[N_MAX][N_MAX], vec[N_MAX];

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

	int N, M, X;

	scanf("%d %d %d\n", &N, &M, &X);
	for (int i = 1; i <= N; i ++) {
		for (int j = 1; j <= M; j ++) {
			scanf("%d ", &a[i][j]);
		}
	}

	for (int i = 1; i <= N; i ++) {
		for (int j = 1; j <= M; j ++) {
			sum[i][j] = sum[i - 1][j] + a[i][j];
		}
	}

	int MAX = 0;
	for (int i = 1; i <= N; i ++) {
		for (int j = i; j <= N; j ++) {

			for (int k = 1; k <= M; k ++) vec[k] = sum[j][k] - sum[i - 1][k];

			int rez = 0, st = 1;
			for (int k = 1; k <= M; k ++) {
				rez += vec[k];
				while (rez > X) {
					st ++;
					rez -= vec[st];
				}
				if ((k - st + 1) * (j - i + 1) > MAX) MAX = (k - st + 1) * (j - i + 1);
			}
		}
	}

	printf("%d\n", MAX);

	return 0;
}