Cod sursa(job #2649606)

Utilizator GiosinioGeorge Giosan Giosinio Data 15 septembrie 2020 14:28:23
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

ifstream f("deque.in");
ofstream g("deque.out");

struct data{
    long long key, ind;
};

long long N,K;
deque <data> d;

void read(){
    f>>N>>K;
    data val;
    for(long long i=1; i<K; ++i){
        f>>val.key, val.ind=i;
        while(!d.empty() && d.back().key >= val.key)
            d.pop_back();
        d.push_back(val);
    }
}

void solve(){
    data val;
    long long sum = 0;
    for(long long i=K; i<=N; ++i){
        f>>val.key; val.ind = i;
        while(!d.empty() && d.front().ind <= i-K)
            d.pop_front();
        while(!d.empty() && val.key <= d.back().key)
            d.pop_back();
        d.push_back(val);
        sum += d.front().key;
    }
    g<<sum;
}

int main()
{
    read();
    solve();
}