Cod sursa(job #2618116)

Utilizator STEFAN-ZOTAZota Stefan-Daniel STEFAN-ZOTA Data 23 mai 2020 18:28:00
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include<bits/stdc++.h>

using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int n,k,i;
int v[5000001];
long long sumaMin;
int main()
{
    f>>n>>k;
    deque<pair<int,int>>coada;

    for(i = 1; i <= n; i++)
        f>>v[i];
    coada.push_back({v[1], 1});

    for(i = 2; i <= k; i++)
    {
        while(coada.size() != 0 && coada.back().first >= v[i])
                coada.pop_back();
        coada.push_back({v[i], i});
    }

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

        if(coada.front().second == i-k)
            coada.pop_front();
        sumaMin += coada.front().first;
    }
    g<<sumaMin;

    return 0;
}