Cod sursa(job #3266679)

Utilizator mewcatPetru Boca mewcat Data 9 ianuarie 2025 20:16:12
Problema Deque Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <deque>

#define ll long long

using namespace std;

int a[5000000];
deque<int> q;

int main()
{
    ifstream fin("deque.in");
    ofstream fout("deque.out");

    int n = 0;
    int k = 0;
    ll sum = 0;
    int j = 0;

    fin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        fin >> a[i];
    }

    q.push_back(a[k - 1]);

    for (int i = k - 2; i >= 0; i--)
    {
        q.push_front(min(q.front(), a[i]));
    }

    sum += q.front();

    for (int i = k; i < n; i++)
    {
        q.pop_front();

        j = q.size() - 1;

        while (q[j] > a[i] && j >= 0)
        {
            q[j] = a[i];
            j--;
        }

        q.push_back(a[i]);

        sum += q.front();
    }

    fout << sum;
}