Cod sursa(job #124049)

Utilizator azotlichidAdrian Vladu azotlichid Data 17 ianuarie 2008 22:43:03
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define CLEAR(X) (memset(X, 0, sizeof(X)))
#define FORI(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define FOR(i, N, M) for (int i = (int)(N); i <= (int)(M); ++i)
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SIZE(X) (int)((X).size())
#define TIPA(a, i) (cerr << #a << "[" #i " = " << (i) << "] = " << (a)[i] << endl)
#define TIP(x) (cerr << #x << " = " << (x) << endl)

#define MP make_pair
#define PB push_back
#define INF 0x3F3F3F3F

typedef long long LL;

#define NMAX 305

int a[NMAX][NMAX], s[NMAX][NMAX];
int M, N, X, Ans = 0, nr;

int main(void) {
	freopen("teren.in", "r", stdin);
	freopen("teren.out", "w", stdout);
	scanf("%d %d %d", &M, &N, &X);
	FOR(i, 1, M) {
		s[i][0] = 0;
		FOR(j, 1, N) {
			scanf("%d", &a[i][j]);
			s[i][j] = s[i][j-1]+a[i][j];
		}
	}

	FOR(l1, 1, N) FOR(l2, l1, N) {
		int j = 1;
		nr = 0;
		FOR(i, 1, M) {
			nr += s[i][l2] - s[i][l1-1];
			while (nr > X) {
				nr -= s[j][l2] - s[j][l1-1];
				++j;
			}
			if ((l2-l1+1)*(i-j+1) > Ans)
				Ans = (l2-l1+1)*(i-j+1);
		}
	}

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

	return 0;
}