Cod sursa(job #2614770)

Utilizator ddeliaioanaaDumitrescu Delia Ioana ddeliaioanaa Data 12 mai 2020 17:47:38
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
std::ifstream fin("deque.in");
std::ofstream fout("deque.out");

int n, k;
int deque[5000001], v[5000001];

void push_back(int deque[], int val, int &back)
{
    deque[++back] = val;
}

void pop_back(int deque[], int &back)
{
    back--;
}

void pop_front(int deque[], int val, int &front)
{
    front++;
}

int main()
{
    int i, back = -1, front = 0;
    long long mins = 0;
    fin >> n >> k;
    for(i = 0; i < n; i++)
        fin >> v[i];
    push_back(deque, 0, back); // 0
    for(i = 1; i < n; i++)
    {
        while(v[i] <= v[deque[back]] && front <= back)
            pop_back(deque, back);

        push_back(deque, i, back);

        if(i >= k - 1)
        {
            mins += v[deque[front]];
            //std::cout<< "Min: " << v[deque[front]] <<'\n';
        }

        if(i - k + 1 == deque[front])
            pop_front(deque, i, front);

    }

    fout << mins;

    return 0;
}