Mai intai trebuie sa te autentifici.
Cod sursa(job #2272968)
Utilizator | 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);
}