Cod sursa(job #583304)

Utilizator Catah15Catalin Haidau Catah15 Data 19 aprilie 2011 16:35:49
Problema Teren Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
// O(N^4)

#include <iostream>
#include <string>

using namespace std;

#define maxN 305


int a[maxN][maxN];


int main()
{
	freopen ("teren.in", "r", stdin);
	freopen ("teren.out", "w", stdout);
	
	int N, M, X;
	
	scanf ("%d %d %d", &N, &M, &X);
	
	
	for (int i = 1; i <= N; ++ i)
		for (int j = 1; j <= M; ++ j)
		{
			int e;
			
			scanf ("%d", &e);
			
			a[i][j] = a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1] + e;
		}
	
	
	int rsp = 0;
	
	for (int i = 1; i <= N; ++ i)
		for (int j = 1; j <= M; ++ j)
			for (int ii = i; ii <= N; ++ ii)
				for (int jj = j; jj <= M; ++ jj)
				{
					int S = 0;
					
					S = a[ii][jj] - a[ii][j - 1] - a[i - 1][jj] + a[i - 1][j - 1];
					
					if (S <= X)
						rsp = max (rsp, (jj - j + 1) * (ii - i + 1));
				}
	
	
	printf ("%d", rsp);
	
	return 0;
}