Pagini recente » Cod sursa (job #1635643) | Cod sursa (job #1633914) | Cod sursa (job #2684614) | Cod sursa (job #3130629) | Cod sursa (job #3216099)
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
#define int long long
deque<int>Q;
int rez = 0;
ifstream fin("deque.in");
ofstream fout("deque.out");
int v[5000001],n;
int32_t main(){
/// le tin in ordine crescatoare dupa indice si descresc
/// dupa valoare
int k ;
fin>>n>>k;
// vector<int>rez;
for(int i=1;i<=n;i++){
int x; fin>>x;
v[i]=x;
/// scot ce e in plus din fata
while(!Q.empty() && Q.back()<=i-k)
Q.pop_back();
while(!Q.empty() && x < v[Q.front()])
Q.pop_front();
Q.push_front(i);
if(i>=k)
rez += v[Q.back()];
}
fout<<rez;
return 0;
}