Cod sursa(job #1601496)

Utilizator vazanIonescu Victor Razvan vazan Data 15 februarie 2016 22:44:35
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<cstdio>
#include<deque>
#include<queue>
using namespace std;
int main(){
    freopen("deque.in", "r", stdin);
    freopen("deque.out", "w", stdout);
    int n, k, elem, i;
    long long sum=0;
    deque< pair<int, int> > dq;
    scanf("%d%d", &n, &k);
    for(i=1; i<=n; i++){
        scanf("%d", &elem);
        while(!dq.empty() && elem<dq.back().first)
            dq.pop_back();
        dq.push_back(make_pair(elem, i));
        if(dq.front().second+k<=i)
            dq.pop_front();
        if(i>=k) sum+=dq.front().first;
    }
    printf("%lld", sum);
    return 0;
}