Cod sursa(job #1861763)

Utilizator raducostacheRadu Costache raducostache Data 29 ianuarie 2017 11:46:58
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <deque>

using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int n,k;
int i;
struct a{
    long long poz;
    long long val;
}x;
deque <a>q;
int main()
{
    f >> n >> k;

    for(i = 1 ; i <= k ; ++i){
        f >> x.val;
        x.poz = i;
        while(!q.empty() && q.back().val > x.val)
            q.pop_back();
        q.push_back(x);
    }
    a smin = q.front();
    int capats = 1;
    int capatd = k;
    for(i = k + 1 ; i <= n ; ++i){
        f >> x.val;x.poz = i;
        capats++;
        capatd++;
        if(q.front().poz < capats)q.pop_front();
        while(!q.empty() && q.back().val > x.val)
            q.pop_back();
        q.push_back(x);
        smin.val += q.front().val;
    }
    g << smin.val;
    return 0;
}