Cod sursa(job #779055)

Utilizator adascaluAlexandru Dascalu adascalu Data 16 august 2012 16:04:16
Problema Deque Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
using namespace std;
#include<fstream>
#include<deque>
#define pair pair<int,int>
#define mp make_pair
#define inF "deque.in"
#define outF "deque.out"
struct QComp
{
	bool operator()(const int&a,const int &b)const
	{
		return a>b;
	}
};
int main ()
{
	int i, n,k,s=0,x;
	deque<pair> v;
	ifstream f(inF);
	f>>n>>k;
	for(i=1;i<=k;i++)
	{
		f>>x;
		while(!v.empty() &&x<v.back().first)
			v.pop_back();
		v.push_back(mp(x,i));
	}
	s+=v.front().first;
	v.pop_front();
	for(i=k+1;i<=n;i++)
	{
		f>>x;
		while(!v.empty() && x<v.back().first)
			v.pop_back();	
		if(v.back().second-v.front().second==k-1)
			v.pop_front();
		v.push_back(mp(x,i));
		s+=v.front().first;
	}
	ofstream g(outF);
	f.close();
	g<<s;
	g.close();
	return 0;
}