Pagini recente » Cod sursa (job #1781570) | Cod sursa (job #1971043) | Cod sursa (job #532451) | Cod sursa (job #908979) | Cod sursa (job #310028)
Cod sursa(job #310028)
#include <fstream>
#include <iterator>
#include <queue>
using namespace std;
#define NUME "deque"
ifstream fi(NUME".in");
ofstream fo(NUME".out");
deque<int> Q, elem;
int main()
{
int N, K, x;
long long calc = 0;
fi >> N >> K;
for (int i = 0; i < N; ++i) {
fi >> x;
if (i >= K)
elem.pop_back();
elem.push_front(x);
while (!Q.empty() && x < elem[i-Q.back()])
Q.pop_back();
Q.push_back(i);
while (!Q.empty() && i - Q.front() >= K)
Q.pop_front();
/*
for (int j = 0; j < Q.size(); ++j)
fo << elem[i-Q[j]] << " ";
fo << "\n";
*/
if (i >= K-1)
calc += elem[i-Q.front()]; // minimul
}
fo << calc << endl;
return 0;
}