Cod sursa(job #677745)

Utilizator nandoLicker Nandor nando Data 10 februarie 2012 16:37:05
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
using namespace std;

FILE* fin = fopen("teren.in", "r");
FILE* fout = fopen("teren.out", "w");

#define MAXN 310

template <typename T> 
inline T max(T a, T b)
{
	return a > b ? a : b;	
}

int n, m, x, s[MAXN][MAXN], a[MAXN][MAXN], maxA = 0;

int compute(int a, int b)
{
	int beg = 1, end = 1, num = s[b][1] - s[a - 1][1];
	while (end < m) {
	
		do {
			++end;
			num += s[b][end] - s[a - 1][end];
		} while (num < x && end < m);
		
		while (num > x && beg < end) {
			num -= s[b][beg] - s[a - 1][beg];
			++beg;
		}
		
		if (num <= x) {
			maxA = max(maxA, (b - a + 1) * (end - beg + 1));
		}
	}
}

int main()
{
	fscanf(fin, "%d %d %d\n", &n, &m, &x);
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			fscanf(fin, "%d ", &a[i][j]);	
			s[i][j] = s[i - 1][j] + a[i][j];
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j = i; j <= n; ++j) {
			compute(i, j);	
		}	
	}
	
	fprintf (fout, "%d\n", maxA);
	
	fclose(fin);
	fclose(fout);
	return 0;
}