Pagini recente » Cod sursa (job #2217531) | Cod sursa (job #3296364)
#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
const int N=5e6+5;
deque<pair<int,int>> dq;
int v[N];
void add(int x, int i)
{
while(!dq.empty()&&dq.back().first>=x) dq.pop_back();
dq.pb({x,i});
}
void del(int x, int i)
{
while(!dq.empty()&&dq.front().second<=i) dq.pop_front();
}
signed main()
{
ifstream cin("deque.in");ofstream cout("deque.out");
int n,k;
cin>>n>>k;
for(int i=1;i<=n;++i) {cin>>v[i];v[i]*=-1;}
int ans=0;
for(int i=1;i<=n;++i)
{
add(v[i],i);
if(i>k) del(v[i-k],i-k);
if(i>=k) ans+=dq.front().first;
}
cout<<-ans;
}