Cod sursa(job #2970240)

Utilizator sandry24Grosu Alexandru sandry24 Data 24 ianuarie 2023 18:34:18
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
 
void solve(){
    int n, k;
    cin >> n >> k;
    deque<pi> a;
    int ans = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        while(!a.empty() && a.back().f >= x)
            a.pop_back();
        a.push_back(mp(x, i));
        if(i >= k-1){
            while(a.front().s < i-k+1)
                a.pop_front();
            ans += a.front().f;
            //cout << a.front().f << '\n';
        }
    }
    cout << ans << '\n';
}  
 
int main(){
    freopen("deque.in", "r", stdin);
    freopen("deque.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}