Cod sursa(job #508266)

Utilizator blastoiseZ.Z.Daniel blastoise Data 7 decembrie 2010 22:36:14
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>
#include <deque>

using namespace std;

deque<pair<int,int> > A;
deque<pair<int,int> >::reverse_iterator it;

int i,d,n,x;
long long smin;

int main()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);

	scanf("%d%d",&n,&d);
	for(i=1;i<=d;i++)
	{
		scanf("%d",&x);
		it=A.rbegin();
		while(it!=A.rend()&&it->first>x)
		{
			A.pop_back();
			it=A.rbegin();
		}
		A.push_back(make_pair(x,i));
	}
	smin=A.front().first;
	for(i=d+1;i<=n;i++)
	{
		scanf("%d",&x);
		it=A.rbegin();
		while(it!=A.rend()&&it->first>x)
		{
			A.pop_back();
			it=A.rbegin();
		}
		A.push_back(make_pair(x,i));
		if(i-A.front().second>=d) A.pop_front();
		smin+=A.front().first;
	}

	printf("%lld\n",smin);

	return 0;
}