Pagini recente » Cod sursa (job #2898082) | Istoria paginii runda/sim_oji2012_1 | Istoria paginii runda/trainingtime/clasament | Cod sursa (job #642753) | Cod sursa (job #3126989)
#include <iostream>
#include <deque>
#include <vector>
#include<fstream>
using namespace std;
int main() {
int N, K;
ifstream fin("deque.in");
ofstream fout("deque.out");
fin >> N >> K;
vector<int> A(N);
for (int i = 0; i < N; i++) {
fin >> A[i];
}
deque<int> dq;
int sum = 0;
for (int i = 0; i < N; i++) {
while (!dq.empty() && A[dq.back()] >= A[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= K - 1) {
sum += A[dq.front()];
}
if (dq.front() <= i - K + 1) {
dq.pop_front();
}
}
fout << sum << endl;
return 0;
}