Cod sursa(job #3296364)

Utilizator iordacheMatei Iordache iordache Data 12 mai 2025 12:22:59
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#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;
}