Cod sursa(job #1513503)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 29 octombrie 2015 17:20:59
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
# include <bits/stdc++.h>

using namespace std;

const int Lmax = 5000005;

deque <int> Q;

int a[Lmax];
int n, k, sum = 0;

int main ()

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

    scanf("%d %d\n", &n, &k);

    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);

    for (int i = 1; i <= n; ++i) {
        while (Q.size() && a[i] < a[Q.back()]) Q.pop_back();
        Q.push_back(i);
        if (Q.front() == i - k) Q.pop_front();
        if (i >= k) sum += a[Q.front()];

    }

    printf("%d\n", sum);
    return 0;

}