Cod sursa(job #1256116)

Utilizator avaspAva Spataru avasp Data 5 noiembrie 2014 20:10:19
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<cstdio>
#include<vector>
#include<deque>
using namespace std;

deque<long long>D,poz;
long long sum,x;
int i,n,k;

int main(){
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    scanf("%d%d",&n,&k);

    for(i=1;i<=k;i++){
        scanf("%lld",&x);
        while(D.size()>=1&&x<=D.back()){
            D.pop_back();
            poz.pop_back();
        }
        D.push_back(x);
        poz.push_back(i);
    }
    long long sum=0;
    sum+=D.front();
    //printf("%lld\n",D.front());
    for(i=k+1;i<=n;i++){
        scanf("%lld",&x);
        while(D.size()>=1&&x<=D.back()){
            D.pop_back();
            poz.pop_back();
        }
        D.push_back(x);
        poz.push_back(i);
        while(poz.back()-poz.front()+1>k){
            D.pop_front();
            poz.pop_front();
        }
        sum+=D.front();
        //printf("%lld\n",D.front());
    }
    printf("%lld",sum);
    return 0;
}