Pagini recente » Cod sursa (job #2678732) | Cod sursa (job #488923) | Cod sursa (job #131060) | Cod sursa (job #2571774) | Cod sursa (job #796280)
Cod sursa(job #796280)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
deque<int> dq;
deque<int>::const_iterator it, eit;
long long sir[5000010];
int N, K;
int main(int argc, char const *argv[])
{
fin >> N >> K;
for (int i = 1; i <= N; ++i) {
fin >> sir[i];
}
int result = 0;
for (int i = 1; i <= N; ++i) {
while (!dq.empty() && dq.front() < i - K + 1) {
dq.pop_front();
}
while (!dq.empty() && sir[i] < sir[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= K) {
result += sir[dq.front()];
}
//DEBUG
// for (it = dq.begin(), eit = dq.end(); it != eit; ++it) {
// fout << sir[*it] << ' ';
// }
// fout << endl;
//END DEBUG
}
fout << result;
return 0;
}