Cod sursa(job #3353379)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 6 mai 2026 18:14:50
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>
#define int long long
#define cin ci
#define cout co
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
int n, k;
vector<int> v;
deque<int> dq;
int32_t main()
{
    cin >> n >> k;
    v.resize(n + 5);
    for(int i = 1; i <= n; i ++)
        cin >> v[i];

    int ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        while(!dq.empty() && v[dq.front()] >= v[i])
            dq.pop_front();

        dq.push_front(i);

        if(i == k)
            ans += v[dq.back()];

        if(i > k)
        {
            while(!dq.empty() && dq.back() < i - k + 1)
                dq.pop_back();

            ans += v[dq.back()];
        }

    }
    cout << ans;
    return 0;
}