Cod sursa(job #677736)

Utilizator milijrCristian Militaru milijr Data 10 februarie 2012 16:33:49
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <iostream>
#include <queue>

using namespace std;

#define MAXN 305

queue<int> coada;
int teren[MAXN][MAXN], n, m;

int main()
{
	ifstream in ("teren.in");
	ofstream out("teren.out");
	int i, j, k;
	in >> n >> m >> k;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
		{
			in >> teren[i][j];
			teren[i][j] += teren[i - 1][j];
		}
	
	int l1, l2, s = 0, nr, dimMax = 0, dim;
	for(l1 = 1; l1 <= n; l1 ++)
		for(l2 = l1; l2 <= n; l2 ++)
		{
			for(i = 1; i <= m; i++)
			{
				nr = teren[l2][i] - teren[l1 - 1][i];
				coada.push(nr);
				s += nr;
				while(s > k && !coada.empty())
				{
					s -= coada.front();
					coada.pop();
				}
				dim = coada.size() * (l2 - l1 + 1);
				if(dim > dimMax)
					dimMax = dim;
			}
			while(!coada.empty())
				coada.pop();
			s = 0;
		}
	out << dimMax;
}