Cod sursa(job #583316)

Utilizator Catah15Catalin Haidau Catah15 Data 19 aprilie 2011 17:05:47
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#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 - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + e;
		}			
	
	
	int rsp = 0;
	
	
	for (int i = 1; i <= N; ++ i)
		for (int ii = i; ii <= N; ++ ii)
		{
			int start = 1, S = 0, j = 0;
			
			for (int end = 1; end <= M; ++ end)
			{
				S += a[ii][end] - a[ii][end - 1] - a[i - 1][end] + a[i - 1][end - 1];
				
				j = start;
				
				if (S > X)
					for ( ; S > X && start <= M; ++ start)
						S -= a[ii][start] - a[ii][start - 1] - a[i - 1][start] + a[i - 1][start - 1]; 
				
				if (S <= X)
					rsp = max (rsp, (ii - i + 1) * (end - start + 1));
				
			}
		}
	
	
	printf ("%d", rsp);
	
	return 0;
}