Pagini recente » Cod sursa (job #629285) | Cod sursa (job #1921530) | Cod sursa (job #2060669) | Cod sursa (job #717240) | Cod sursa (job #3000362)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define inputStream cin
#define outputStream cout
#else
#define INPUT_PATH "deque.in"
#define OUTPUT_PATH "deque.out"
ifstream inputStream(INPUT_PATH);
ofstream outputStream(OUTPUT_PATH);
#endif
int main() {
int n, k, value;
inputStream >> n >> k >> value;
deque<pair<int, int>> dq;
long long answer = 0;
dq.push_back(make_pair(value, 1));
for (int i = 2; i <= n; ++i) {
int value;
inputStream >> value;
while (!dq.empty() && value <= dq.back().first)
dq.pop_back();
dq.push_back(make_pair(value, i));
while(!dq.empty() && i - dq.front().second >= k)
dq.pop_front();
if (i >= k)
answer += dq.front().first;
}
outputStream << answer;
#ifdef ONLINE_JUDGE
inputStream.close();
outputStream.close();
#endif
return 0;
}