Pagini recente » Cod sursa (job #1449625) | Cod sursa (job #1333343) | Cod sursa (job #1005262) | Cod sursa (job #2749024) | Cod sursa (job #2406158)
#include <deque>
#include <utility>
#include <fstream>
using std::pair;
using std::deque;
using std::make_pair;
std::ifstream fin("deque.in");
std::ofstream fout("deque.out");
int main() {
int n, k;
fin >> n >> k;
int64_t sol = 0;
deque<pair<int, int>> dq;
for (int i = 0; i < n; i++) {
int x; fin >> x;
while (!dq.empty() && dq.back().first >= x)
dq.pop_back();
dq.push_back(make_pair(x, i));
if (dq.front().second == i - k)
dq.pop_front();
if (i >= k - 1)
sol += dq.front().first;
}
fout << sol << '\n';
fout.close();
return 0;
}