Cod sursa(job #3264687)

Utilizator irina_opreaIrina Oprea irina_oprea Data 23 decembrie 2024 13:20:30
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

long long v[5000010];
deque <long long> dq;

int main()
{
    ifstream cin ("deque.in");
    ofstream cout ("deque.out");

    long long n, k, a, sum=0, intervals=0;
    cin >> n >> k;
    dq.push_front(1);
    cin >> v[1];
    for (int i=2; i<=n; i++)
    {
        cin >> a;
        v[i] = a;
        while ((!dq.empty()) && (a < v[dq.back()]))
        {
            dq.pop_back();
        }
        dq.push_back(i);
        if ((dq.back() - dq.front() + 1) > k)
        {
            dq.pop_front();
            intervals = 1;
        }
        else if (intervals == 1)
        {
            sum += v[dq.front()];
        }
    }
    cout << sum << '\n';
    return 0;
}