Cod sursa(job #463781)

Utilizator darrenRares Buhai darren Data 17 iunie 2010 14:25:07
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<fstream>
#include<deque>
using namespace std;

int n, k, s[50001], mx = -10000000, ifn, jfn;
deque<pair<int, int> > d;

int main()
{
	ifstream fin("secv2.in");
	ofstream fout("secv2.out");
	
	fin >> n >> k;
	for (int i = 1, aux; i <= n; ++i)
	{
		fin >> aux;
		s[i] = s[i - 1] + aux;
	}
	
	for (int i = k; i <= n; ++i)
	{
		while (!d.empty() && d.back().first > s[i - k])
			d.pop_back();
		d.push_back(make_pair(s[i - k], i - k + 1));
		
		if (s[i] - d.front().first > mx)
		{
			mx = s[i] - d.front().first;
			ifn = d.front().second;
			jfn = i;
		}
	}
	
	fout << ifn << ' ' << jfn << ' ' << mx;
}