Cod sursa(job #2888159)

Utilizator Alexandru_PotangaPotanga Alexandru Alin Alexandru_Potanga Data 10 aprilie 2022 18:59:20
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int main()
{
    int n, k, i, st = 0, dr = -1, minim = 0;
    f >> n >> k;
    int deqman[n+1];
    int v[n+1];
    for(i = 0; i < n; i++)
        f >> v[i];

    for(i = 0; i < k; i++)
    {
        while(st <= dr && v[i] <= v[deqman[dr]])
            dr--;
        dr++;
        deqman[dr] = i;
    }
    minim = minim + v[deqman[st]];

    for(i = k; i < n; i++)
    {
        while(st <= dr && deqman[st] <= (i - k))
            st++;

        while(st <= dr && v[i] <= v[deqman[dr]])
            dr--;
        dr++;
        deqman[dr] = i;
        minim = minim + v[deqman[st]];
    }
    g << minim;
    return 0;
}