Cod sursa(job #2761578)

Utilizator 6kmeleon6Luca Cordus 6kmeleon6 Data 2 iulie 2021 19:18:36
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("deque.in");
ofstream out("deque.out");

struct verif
{
    int val;
    int poz;
};

deque <verif> mini;

int main()
{
    int N, K, i;
    long long s=0;
    verif x;
    in >> N >> K;
    for(i = 0; i < N; i++)
    {
        in >> x.val;
        x.poz = i;
        while(mini.size() > 0 && x.val <= mini.back().val)
        {
            mini.pop_back();
        }

        mini.push_back(x);

        if(mini.front().poz == i - K)
            mini.pop_front();

        if (i >= K - 1)
            s += mini.front().val;
    }
    out << s;
    return 0;
}