Cod sursa(job #1791303)

Utilizator roxannemafteiuMafteiu-Scai Roxana roxannemafteiu Data 29 octombrie 2016 11:28:49
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

long long N, K;
vector<long> numbers;
deque<long> minim;

void read() {
    fin >> N >> K;
    for (long i = 0; i < N; ++i) {
        long x;
        fin >> x;
        numbers.emplace_back(x);
    }
}

void solve() {
    long long sum = 0;
    for (int i = 0; i < N; ++i) {
        while (!minim.empty() && numbers[i] <= numbers[minim.back()]) {
            minim.pop_back();
        }

        minim.push_back(i);

        if (minim.front() == i - K) {
            minim.pop_front();
        }

        if (i >= K- 1) {
            sum += numbers[minim.front()];
        }
    }

    fout << sum;
}

int main() {
    read();
    solve();

    return 0;
}