Cod sursa(job #2921664)

Utilizator tzancauraganuTzanca Uraganu tzancauraganu Data 1 septembrie 2022 12:34:05
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
#include <unordered_map>
#include <memory>
#include <deque>

using namespace std;

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

    deque<pair<int, int> > Q;

    int N, K;
    f >> N >> K;
    long long sum = 0;
    for (int i = 0; i < N; i++) {
        int X;
        f >> X;
        while (!Q.empty() && Q.back().first >= X)
            Q.pop_back();
        Q.push_back(make_pair(X, i));
        while (!Q.empty() && Q.front().second <= i - K)
            Q.pop_front();
        
        if (i + 1 >= K)
            sum += Q.front().first;
    }

    g << sum << '\n';
    

    f.close();
    g.close();
    return 0;
}