Pagini recente » Cod sursa (job #3146515) | Cod sursa (job #2852313) | Cod sursa (job #3164542) | Borderou de evaluare (job #2178738) | Cod sursa (job #796278)
Cod sursa(job #796278)
#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) {
result += sir[dq.front()];
dq.pop_front();
}
while (!dq.empty() && sir[i] < sir[dq.back()]) {
dq.pop_back();
}
dq.push_back(i);
//DEBUG
// for (it = dq.begin(), eit = dq.end(); it != eit; ++it) {
// fout << sir[*it] << ' ';
// }
// fout << endl;
//END DEBUG
}
// if (!dq.empty()) {
// result += sir[dq.front()];
// dq.pop_back();
// }
fout << result;
return 0;
}