Pagini recente » Cod sursa (job #2567477) | Cod sursa (job #1624227) | Cod sursa (job #820042) | Cod sursa (job #1497775) | Cod sursa (job #2352616)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int n, m;
int sol;
deque<pair<int, int>> s;
int main() {
fin >> n >> m;
for (int i = 1; i < m; ++i) {
int k;
fin >> k;
while (!s.empty() && k < s.back().first) {
s.pop_back();
}
s.push_back({k, i});
}
for (int i = m; i <= n; ++i) {
int k;
fin >> k;
while (!s.empty() && k < s.back().first) {
s.pop_back();
}
s.push_back({k, i});
while (s.front().second <= i - m) {
s.pop_front();
}
sol += s.front().first;
}
fout << sol;
fout.close();
return 0;
}