Cod sursa(job #223125)

Utilizator ProtomanAndrei Purice Protoman Data 26 noiembrie 2008 22:50:45
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <algorithm>
#include <stdio.h>
#define mx 310

using namespace std;

int n, m, x, maxim, st, imp, xm;
int a[mx][mx];

int main()
{
	freopen("teren.in","r",stdin);
	freopen("teren.out","w",stdout);
	scanf("%ld %ld %ld", &n, &m, &xm);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			scanf("%ld", &x);
			a[i][j] = a[i - 1][j] + x;
		}
	for (int l = 1; l <= n; l++)
		for (int i = 1; i <= n - l + 1; i++)
		{
			st = 0;
			imp = 0;
			for (int j = 1; j <= m; j++)
			{
				imp += (a[i + l - 1][j] - a[i - 1][j]);
				while (imp > xm && st <= j)
				{
					st++;
					imp -= (a[i + l - 1][st] - a[i - 1][st]);
				}
				maxim = max(l * (j - st), maxim);
			}
		}
	printf("%ld\n", maxim);
	fclose(stdin);
	fclose(stdout);
	return 0;
}