Pagini recente » Cod sursa (job #2386037) | Cod sursa (job #428030) | Cod sursa (job #482635) | Cod sursa (job #1636272) | Cod sursa (job #2649606)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
struct data{
long long key, ind;
};
long long N,K;
deque <data> d;
void read(){
f>>N>>K;
data val;
for(long long i=1; i<K; ++i){
f>>val.key, val.ind=i;
while(!d.empty() && d.back().key >= val.key)
d.pop_back();
d.push_back(val);
}
}
void solve(){
data val;
long long sum = 0;
for(long long i=K; i<=N; ++i){
f>>val.key; val.ind = i;
while(!d.empty() && d.front().ind <= i-K)
d.pop_front();
while(!d.empty() && val.key <= d.back().key)
d.pop_back();
d.push_back(val);
sum += d.front().key;
}
g<<sum;
}
int main()
{
read();
solve();
}