Cod sursa(job #2203258)
Utilizator | Bogdan Marin bogdanmarin69 | Data | 11 mai 2018 18:25:17 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include <fstream>
#include <queue>
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
deque<pair<int, int> > q;
int main()
{
int n, k;
long long ans = 0;
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
int x;
cin >> x;
while(!q.empty() && q.back().second >= x) {
q.pop_back();
}
q.push_back({i, x});
if(q.front().first <= i - k) {
q.pop_front();
}
if(i >= k) {
ans = ans + q.front().second;
}
}
cout << ans;
return 0;
}