Cod sursa(job #2618041)

Utilizator STEFAN-ZOTAZota Stefan-Daniel STEFAN-ZOTA Data 23 mai 2020 16:02:46
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
// am refacut programul in c++ pentru ca python era prea lent
#include <bits/stdc++.h>

using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int main()
{
    int n, k, i, v[101], x, sumaMin=0;
    f>>n>>k;
    deque<pair<int, int> > coada;
    for(i = 1; i <= n; i++)
        f>>v[i];

    coada.push_back({v[1], 1});
    if (k == 1)
        sumaMin = v[1];
        for(i = 2; i <= n; i++)
        {
            if(coada.size() != 0 && coada.front().second <= i-k)
                {
                    coada.pop_front();
                }
            if(coada.size() != 0)
                while(coada.back().first >= v[i])
                    {
                        coada.pop_back();
                    }

            coada.push_back({v[i], i});
            if(i>=k)
                sumaMin += coada.front().first;
        }
    g<<sumaMin;

    return 0;
}