Cod sursa(job #2371989)
Utilizator | Tir Vlad Ioan Vlad3108 | Data | 6 martie 2019 20:43:49 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.58 kb |
#include <bits/stdc++.h>
using namespace std;
int main(){
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int n,k;
scanf("%d %d",&n,&k);
deque<pair<int,int> > D;
long long sum=0;
for(int i=1;i<=n;++i){
int x;
scanf("%d",&x);
while(!D.empty()&&D.back().second>=x)
D.pop_back();
D.push_back({i,x});
if(i>=k){
sum+=D.front().second;
if(D.front().first==i-k+1)
D.pop_front();
}
}
printf("%lld\n",sum);
return 0;
}