Cod sursa(job #2566296)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 2 martie 2020 20:22:10
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>

#define MAXN        200005
#define FILENAME    std::string("deque")

int N, K;
std::deque <std::pair <int, int>> deque;

std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int main()
{
    input >> N >> K;
    long long sum = 0;
    for (int i=1, x; i<=N; ++i) {
        input >> x;
        while (!deque.empty() && deque.front().first   >= x) deque.pop_front();
        if    (!deque.empty() && deque.back().second+K <= i) deque.pop_back();
        deque.push_front({x, i});
        if (i >= K) sum += 1ll*deque.back().first;
    }   output << sum;

    return 0;
}