Cod sursa(job #896191)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 27 februarie 2013 14:18:51
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("teren.in");
ofstream fout("teren.out");
int N, M, X, sol;
int a[311][311], s[311][311];

int main()
{
	fin >> N >> M >> X;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			fin >> a[i][j], s[i][j] = s[i - 1][j] + a[i][j];

	for (int l1 = 1; l1 <= N; l1++)
		for (int l2 = l1; l2 <= N; l2++)
		{
			int left = 0, sum = 0, suml = 0;
			for (int c = 1; c <= M; c++)
			{
				sum = sum + s[l2][c] - s[l1 - 1][c];
				while (sum - suml > X)
				{
					left++;
					suml = suml + s[l2][left] - s[l1 - 1][left];
				}
				if (sol < (l2 - l1 + 1) * (c - left))
				{
					sol = (l2 - l1 + 1) * (c - left);
				}
			}
		}

	fout << sol << '\n';
	fout.close();
	return 0;
}