Cod sursa(job #1604009)

Utilizator krityxAdrian Buzea krityx Data 17 februarie 2016 21:34:14
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>
#include <deque>
#define NMAX 50001
using namespace std;

int main()
{
	int n, k, v[NMAX], pSum[NMAX], i, smax = - (1<<30), start, end;
	deque<int> d;
	ifstream f("secv2.in");
	f >> n >> k;
	pSum[0] = 0;
	for (i = 1; i <= n; i++)
	{
		f >> v[i];
		pSum[i] = pSum[i - 1] + v[i];
	}
	f.close();

	d.push_back(1);
	for (i = 2; i <= n; i++)
	{
		while (!d.empty() && pSum[d.front()] > pSum[i])
		{
			d.pop_front();
		}
		if (!d.empty() && i - d.front() >= k && (v[i] - v[d.front()] > smax))
		{
			smax = pSum[i] - pSum[d.front()];
			start = d.front() + 1;
			end = i;
		}
		d.push_back(i);
	}

	ofstream g("secv2.out");
	g << start << " " << end << " " << smax;
	g.close();
	return 0;
}