Cod sursa(job #184227)

Utilizator slayer4uVictor Popescu slayer4u Data 23 aprilie 2008 12:26:27
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>

long n, m, k, i, j, l, sum, st, num, max, x[301][301], u[301][301];

int main()
{
	freopen ("teren.in", "rt", stdin);
	freopen ("teren.out", "wt", stdout);

	scanf("%ld %ld %ld", &n, &m, &k);
	
	for (i = 1; i <= n; ++i)
		for (j = 1; j <= m; ++j)
			scanf("%ld", &x[i][j]);

	for (j = 1; j <= m; ++j)
		for (i = 1; i <= n; ++i)
			u[i][j] = u[i - 1][j] + x[i][j];

	for (i = 1; i <= n; ++i)
		for (j = i; j <= n; ++j)
		{
			num = 0;
			sum = 0;
			st = 1;
			for (l = 1; l <= m; ++l)
			{
				sum += u[j][l] - u[i - 1][l];
				++num;
				if (sum > k)
				{
					while (sum > k)
						sum -= u[j][st] - u[i - 1][st], --num, ++st;
				}
				else
					max = max < (j - i + 1) * num ? (j - i + 1) * num : max;
			}
		}

	printf("%ld\n", max);

	return 0;
}