Cod sursa(job #2272945)

Utilizator StefanZamfirStefan Zamfir StefanZamfir Data 30 octombrie 2018 19:47:42
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
	
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;
	
    a.push_front(make_pair(x,0));
	
    for(int i=1;i<k;++i){
	
        cin >> 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;
	
        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;
	
}