Cod sursa(job #1753820)

Utilizator AplayLazar Laurentiu Aplay Data 7 septembrie 2016 11:09:00
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

#define NMAX 5000000

using namespace std;

int N, K;
long long sum = 0, numbers[NMAX];
deque<long long> dq;

void addDQ(long long number) {
    while (!dq.empty() && dq.back() > number) dq.pop_back();
    dq.push_back(number);
}

int main() {
    freopen("deque.in", "r", stdin);
    freopen("deque.out", "w", stdout);

    scanf("%d%d", &N, &K);

    for (int it = 0; it < K; ++it) {
        scanf("%lld", &numbers[it]);
        addDQ(numbers[it]);
    }

    sum += dq.front();

    for (int it = K; it < N; ++it) {
        if (dq.front() == numbers[it - K]) dq.pop_front();
        scanf("%lld", &numbers[it]);
        addDQ(numbers[it]);
        sum += dq.front();
    }

    printf("%lld", sum);

    return 0;
}