Pagini recente » Cod sursa (job #828233) | Cod sursa (job #2220963) | Istoria paginii runda/eusebiu_oji_2003_cls10/clasament | Cod sursa (job #2777008) | Cod sursa (job #2877435)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
long long v[5000001], s = 0;
deque <pair<int, int>> d;
int main() {
int n, subsir;
in >> n >> subsir;
for (int i = 1; i <= n; ++i) {
in >> v[i];
}
for (int i = 1; i <= n; ++i) {
if (!d.empty() && (i - d.front().second) >= subsir)
d.pop_front();
if (!d.empty()) {
if (v[i] <= d.back().first) {
while (!d.empty() && v[i] <= d.back().first)
d.pop_back();
}
d.push_back(make_pair(v[i], i));
}
else
d.push_back(make_pair(v[i], i));
if (i >= subsir && !d.empty())
s += d.front().first;
}
out << s;
}