Cod sursa(job #3180464)
Utilizator | Marius Harabari mariusharabari | Data | 5 decembrie 2023 12:17:24 |
---|---|---|---|
Problema | Deque | Scor | 25 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <bits/stdc++.h>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
deque<int> d;
int n, k, s, a, v[5000005];
int main(){
fin>>n>>k;
int i;
for(i=0;i<n;i++){
fin>>v[i];
}
for(i=0;i<k;i++){
while(!d.empty()&&v[i]<=v[d.back()])
d.pop_back();
d.push_back(i);
}
s=v[d.front()];
for(i=k;i<n;i++){
while(!d.empty()&&v[i]<=v[d.back()])
d.pop_back();
if(!d.empty()&&d.front()==i-k)
d.pop_front();
d.push_back(i);
s+=v[d.front()];
}
fout<<s<<endl;
return 0;
}