Cod sursa(job #1161061)

Utilizator gbibBacotiu Gabi gbib Data 30 martie 2014 23:19:07
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.46 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
int v[5000005];
int main()
{int n,i,k;
long long minim=0;
deque<int>deq;
in>>n>>k;

for(i=1;i<=n;i++)
{
    in>>v[i];
    while(!deq.empty()&&v[deq.back()]>v[i])
    deq.pop_back();
    deq.push_back(i);
    if(deq.front()<=i-k)
        deq.pop_front();
        if(i>=k)
    minim+=v[deq.front()];

}
out<<minim<<endl;
return 0;
}