Cod sursa(job #2205232)

Utilizator mirceagavrizimircea luca gavrizi mirceagavrizi Data 18 mai 2018 15:53:19
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#include<deque>
using namespace std;
deque <int> d1;
deque <int> d2;
int main(){
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    int n,k,nr,s,i,h;
    scanf("%d%d%d",&n,&k,&nr);
    d1.push_front(nr);
    d2.push_front(1);
    s=0;
    h=2;
    while(h<=k){
        scanf("%d",&nr);
        while(!d1.empty()&&nr<=d1.back()){
            d1.pop_back();
            d2.pop_back();
        }
        d1.push_back(nr);
        d2.push_back(h);
        h++;
    }
    s=s+d1.front();
    for(i=k+1;i<=n;i++){
        scanf("%d",&nr);
        if(!d1.empty()&&d2.front()<i-k+1){
            d1.pop_front();
            d2.pop_front();
        }
        while(!d1.empty()&&nr<=d1.back()){
            d1.pop_back();
            d2.pop_back();
        }
        d1.push_back(nr);
        d2.push_back(i);
        s=s+d1.front();
    }
    printf("%d",s);
return 0;
}