Pagini recente » Cod sursa (job #2266535) | Cod sursa (job #1568255) | Istoria paginii runda/usu7/clasament | Cod sursa (job #1070348) | Cod sursa (job #1978372)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
#define pb push_back
#define ll long long
const int NMax = 5e6 + 5;
const int inf = 1e9 + 5;
int N,K;
int v[NMax];
struct elem {
int idx,val;
elem (int _idx = 0,int _val = 0) {
idx = _idx;
val = _val;
}
};
bool operator <(elem a,elem b) {
return a.val > b.val;
}
int main() {
in>>N>>K;
for (int i=1;i <= N;++i) {
in>>v[i];
}
priority_queue<elem> Q;
for (int i=1;i <= K;++i) {
Q.push(elem(i,v[i]));
}
//cout<<Q.top().val<<'\n';
ll sum = Q.top().val;
for (int i=K+1;i <= N;++i) {
Q.push(elem(i,v[i]));
while (Q.top().idx < i-K+1) {
Q.pop();
}
sum += Q.top().val;
//cout<<Q.top().val<<'\n';
}
out<<sum<<'\n';
in.close();out.close();
return 0;
}