Cod sursa(job #2734924)

Utilizator trucker4lifeMoraru Radu-Andrei trucker4life Data 1 aprilie 2021 17:19:42
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <deque>
#include <fstream>

#define time second
#define val first

using namespace std;
typedef pair<int, int> pii;
int n, k, sum = 0;

ifstream fin("deque.in");
ofstream fout("deque.out");

deque<pii> q;

void insert(pii p) {
    while (!q.empty() && p.time - q.front().time +1 > k)
        q.pop_front();
    while (!q.empty() && p.val < q.back().val)
        q.pop_back();
    q.push_back(p);
}

int main() {
    fin >> n >> k;

    for (int i = 0; i < k; i++) {
        int a;
        fin >> a;
        insert({a, i});
    }
    sum += q.front().val;

    for (int i = k; i < n; i++) {
        int a;
        fin >> a;
        insert({a, i});
        sum += q.front().val;
    }
    fout << sum;
}