Cod sursa(job #2272968)

Utilizator gabiluciuLuciu Gabriel gabiluciu Data 30 octombrie 2018 20:09:01
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
int n,k,x;
deque<pair<int,int> > a;
int main(){
    freopen("deque.in" ,"r", stdin);
    freopen("deque.out" ,"w", stdout);
    //cin >> n >> k >> x;
    scanf("%d%d%d\n",&n,&k,&x);
    a.push_front(make_pair(x,0));
    for(int i=1;i<k;++i){
        //cin >> x;
        scanf("%d",&x);
        while(x <= a.back().first &&!a.empty())
            a.pop_back();
        a.push_back(make_pair(x,i));
    }
    long long s = a.front().first;
    for(int i=k;i<n;++i){
        //cin >> x;
        scanf("%d",&x);
        while(x <= a.back().first&&!a.empty())
            a.pop_back();
        a.push_back(make_pair(x,i));
        if(a.front().second<i-k+1)
            a.pop_front();
        s+=a.front().first;
    }
    //cout << s;
    printf("%d",s);
}