Cod sursa(job #3211192)

Utilizator karo_8870Cazacu Christian Matei karo_8870 Data 8 martie 2024 18:17:19
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream cin("deque.in");
ofstream cout("deque.out");

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N, K, x, S = 0;
    cin >> N >> K;

    deque<pair<int, int>> d;

    for (int i = 0; i < K; ++i) {
        cin >> x;

        while (!d.empty() && x < d.front().first) {
            d.pop_front();
        }

        d.push_front(make_pair(x, i));
    }

    for (int i = K; i <= N; ++i) {
        S += d.back().first;

        if (d.back().second <= i - K) {
            d.pop_back();
        }

        cin >> x;

        while (!d.empty() && x < d.front().first) {
            d.pop_front();
        }

        d.push_front(make_pair(x, i));
    }

    cout << S;

    return 0;
}

/*
-7 9 2 4 -1 5 6 7 1

-7 2 4
*/