Pagini recente » Cod sursa (job #653596) | Cod sursa (job #1041286) | Rating Hambasan Ioan (juniorutu) | Cod sursa (job #2034054) | Cod sursa (job #1978374)
#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;
elem (int _idx = 0) {
idx = _idx;
}
};
bool operator <(elem a,elem b) {
return v[a.idx] > v[b.idx];
}
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));
}
//cout<<(double)sizeof(v)/(1024*1024)<<'\n';
//cout<<Q.top().val<<'\n';
ll sum = v[Q.top().idx];
for (int i=K+1;i <= N;++i) {
Q.push(elem(i));
while (Q.top().idx < i-K+1) {
Q.pop();
}
sum += v[Q.top().idx];
//cout<<Q.top().val<<'\n';
}
out<<sum<<'\n';
in.close();out.close();
return 0;
}