Cod sursa(job #443783)

Utilizator IlieeUngureanu Ilie Iliee Data 18 aprilie 2010 13:26:41
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<deque>
#include<cstdio>
#include<utility>
using namespace std;
void read(),solve();
deque<pair<int,int> > q;
int i,s=0,k,n,x;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(i=1;i<k;i++)
	{
		scanf("%d",&x);
		while(!q.empty()&&x<q.back().first)
			q.pop_back();
		if(q.empty())q.resize(0);
		q.push_back(make_pair(x,i));
	}
}
void solve()
{
	for(i=k;i<=n;i++)
	{
		scanf("%d",&x);
		while(!q.empty()&&x<q.back().first)
			q.pop_back();
		if(q.empty())q.resize(0);
		q.push_back(make_pair(x,i));
		if(q.front().second==i-k)
			q.pop_front();
		s+=q.front().first;
	}
	printf("%d\n",s);
	
}