Cod sursa(job #1861768)

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

using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int n,k;
int i;
struct a{
    int poz;
    int val;
}x;
struct b{
    long long poz;
    long long val;
};
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);
    }
    b smin;
    smin.val = q.front().val;
    smin.poz = q.front().poz;
    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;
}