Cod sursa(job #2127625)

Utilizator rebecca0312Andrei Rebecca rebecca0312 Data 10 februarie 2018 20:59:43
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<cstdio>
#include<deque>
#define x first
#define y second
using namespace std;

deque<pair<int, int>> d;

int main(){
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    int n,nr,k;
    long long s=0;
    pair<int, int> a;
    scanf("%d%d", &n, &k);
    for(int i=1;i<=n;i++){
        scanf("%d", &nr);
        if(!d.empty() && d.back().y<=i-k)
            d.pop_back();
        while(!d.empty() && nr<d.front().x)
            d.pop_front();
        pair<int, int> q;
        q.x=nr,q.y=i;
        d.push_front(q);
        if(i>=k && !d.empty())
            s+=d.back().x;
    }
    printf("%lld", s);
    return 0;
}