Cod sursa(job #2200321)
| Utilizator | Data | 30 aprilie 2018 23:43:02 | |
|---|---|---|---|
| Problema | Deque | Scor | 25 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.57 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int main() {
int n, k, x, i;
pair<int, int> a;
deque<pair<int, int> > q;
f >> n >> k;
int sum = 0;
for (i = 1; i <= n; ++i) {
f >> x;
while (!q.empty()) {
a = q.back();
if (a.first >= x)
q.pop_back();
else
break;
}
q.push_back(make_pair(x, i));
a = q.front();
if (i - a.second >= k) {
q.pop_front();
}
if (i >= k) {
a = q.front();
sum += a.first;
}
}
g << sum << '\n';
return 0;
}