Cod sursa(job #2671496)

Utilizator justin.stoicaJustin Stoica justin.stoica Data 12 noiembrie 2020 11:06:28
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;
deque< pair <int, int> >coada;
int main()
{
    ifstream cin("deque.in");
    ofstream cout("deque.out");

    long long int  n, k, sol = 0;
    cin >> n >> k;
    for(int i = 1; i < k - 1; i ++)
    {
        int a;
        cin >> a;
        while(coada.front().first > a && !coada.empty())
            coada.pop_back();
        coada.push_back(make_pair(a, i));
    }
    for(int i = k - 1; i <= n; i ++)
    {
        int a;
        cin >> a;
        while(coada.front().first > a && !coada.empty())
            coada.pop_back();
        coada.push_back(make_pair(a, i));
        while(coada.front().second <= i - k &&!coada.empty() )
        {
            coada.pop_front();
        }
            sol += coada.front().first;
    }
    cout << sol;
    return 0;
}