Pagini recente » Cod sursa (job #2475655) | Cod sursa (job #179777) | Cod sursa (job #211104) | Cod sursa (job #1481979) | Cod sursa (job #2045910)
#include <iostream>
#include <fstream>
#include <deque>
std::ifstream f("deque.in");
std::ofstream g("deque.out");
int v[5000000];
std::deque <int> minDq;
long long rez;
int main()
{
int N, K;
f>>N>>K;
for(int i=1; i<=N; i++)
f>>v[i];
int i;
for(i=1; i<=K; i++) {
while(!minDq. empty() && v [minDq. back()] >= v[i])
minDq. pop_back();
minDq. push_back(i);
}
rez += v[minDq. front()];
for(; i<=N; i++) {
if(!minDq.empty() && minDq.front() <= i-K)
minDq.pop_front();
while(!minDq. empty() && v [minDq. back()] >= v[i])
minDq. pop_back();
minDq. push_back(i);
rez += v[minDq. front()];
}
g<<rez;
return 0;
}