Cod sursa(job #3226110)
Utilizator | Munteanu Mihnea Gabriel InformaticianInDevenire1 | Data | 20 aprilie 2024 09:07:28 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("deque.in");
ofstream fout ("deque.out");
deque <pair <int, int>> dq;
int main() {
int n, k;
long long sum = 0;
fin >> n >> k;
for (int i=1;i<=n;++i) {
int x;
fin >> x;
while (!dq.empty() and i-dq.front().second >= k) dq.pop_front();
while (!dq.empty() and dq.back().first >= x) dq.pop_back();
dq.push_back({x, i});
if (i>=k) {
sum += dq.front().first;
}
}
fout << sum;
return 0;
}