Pagini recente » Cod sursa (job #2585252) | Cod sursa (job #2323169) | oji-10-2 | Cod sursa (job #1762710) | Cod sursa (job #2877440)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
int v[5000001];
long long 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;
}