Cod sursa(job #3220066)
Utilizator | Flavius Andronic gBne | Data | 2 aprilie 2024 10:37:42 |
---|---|---|---|
Problema | Deque | Scor | 60 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
const long long NMax = 5000005;
int main()
{
long long n, k, sum = 0, val;
fin >> n >> k;
deque<pair<long long, int>> dq;
for(long long i=1; i<=n; ++i){
if(!dq.empty()){
if(dq.front().first == i - k){
dq.pop_front();
}
}
fin >> val;
while(!dq.empty() && dq.back().second > val){
dq.pop_back();
}
dq.emplace_back(i, val);
if(i >= k){
sum += dq.front().second;
}
}
fout << sum << '\n';
return 0;
}