Cod sursa(job #2208905)

Utilizator aurelionutAurel Popa aurelionut Data 1 iunie 2018 01:01:12
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 310;
int n, m, k, areaMax = -1;
int a[NMAX][NMAX];
int v[NMAX];

void Read()
{
	ifstream fin("teren.in");
	fin >> n >> m >> k;
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j)
			fin >> a[i][j];
	fin.close();
}

void Solve()
{
	for (int j = 1;j <= m;++j)
		for (int i = 1;i <= n;++i)
			a[i][j] += a[i - 1][j];
	for (int l1 = 0;l1 < n;++l1)
		for (int l2 = l1 + 1;l2 <= n;++l2)
		{
			for (int j = 1;j <= m;++j)
				v[j] = a[l2][j] - a[l1][j];
			int lgMax = 0;
			int p = 1, curr = 0;
			for (int j = 1;j <= m;++j)
			{
				curr += v[j];
				if (curr <= k)
					lgMax = max(lgMax, j - p + 1);
				else
				{
					while (curr > k && p <= j)
					{
						curr -= v[p];
						++p;
					}
				}
			}
			areaMax = max(areaMax, lgMax * (l2 - l1));
		}
}

void Write()
{
	ofstream fout("teren.out");
	fout << areaMax << "\n";
	fout.close();
}

int main()
{
	Read();
	Solve();
	Write();
	return 0;
}