Cod sursa(job #728654)

Utilizator iulynaCretu Irina iulyna Data 28 martie 2012 20:46:41
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<iostream>
#include<fstream>
#include<deque>
using namespace std;
deque<int> q,poz;
long long s;
int n,k,x,ifi;
int main()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	int i;
	scanf("%d%d%d",&n,&k,&x);
	q.push_back(x);
	poz.push_back(1);
	ifi=1;
	for(i=2;i<=n;i++)
	{
		scanf("%d",&x);
		ifi++;
		while(x<q.back()&&!q.empty())
		{
			q.pop_back();
			poz.pop_back();
		}
		q.push_back(x);
		poz.push_back(ifi);
		if(ifi-poz.front()==k)
		{
			q.pop_front();
			poz.pop_front();
		}
		if(ifi>=k)
			s=s+q.front();
	}
	printf("%lld",s);
	
	return 0;
}