Cod sursa(job #1387183)

Utilizator azkabancont-vechi azkaban Data 13 martie 2015 19:55:02
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <bits/stdc++.h>
using namespace std;
#define pos first 
#define val second
long long n,i,j,k,m,aux,pivot(0),sol(0);
deque < pair < int,int > > Deq;
int main(void)
{
 ifstream cin("deque.in");
 ofstream cout("deque.out");
 cin>>n>>k;
 for (i=1;i<=n;++i)
   {
   	cin>>aux;
   	while(!Deq.empty() && Deq.back().val>aux) Deq.pop_back();
   	Deq.push_back({i,aux});
   	if (i>=k)
   	     {
   	      ++pivot;
   	      sol+=Deq.front().val;
   	      while(Deq.front().pos<=pivot) Deq.pop_front();
		 }
   }
 cout<<1LL*sol<<"\n";
 return 0;
}