Cod sursa(job #2376869)

Utilizator AntoniuFicAntoniu Ficard AntoniuFic Data 8 martie 2019 18:16:14
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
#include <deque>

using namespace std;

int n, k;

int main() {
    ifstream f("deque.in");
    ofstream g("deque.out");
    f>>n>>k;
    long long suma = 0;
    deque<pair<int, int> >D;
    f>>suma;
    D.push_back({suma, 0});
    suma = 0;
    if(k == 1)
        suma+=D.front().first;
    for(int i=1; i<n; i++){
        int x;
        f>>x;
        while(D.back().first>x)
            D.pop_back();
        D.push_back({x, i});
        if(D.front().second == i-k)
            D.pop_front();
        if(i>=k - 1)
            suma += D.front().first;
    }
    g<<suma;
    return 0;
}