Cod sursa(job #2888998)

Utilizator Andoss1710Balanica Andrei Andoss1710 Data 12 aprilie 2022 01:20:01
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int dq[5000003],v[5000003];
int main()
{
    int n, k, coada = -1, capat = 0, suma_min = 0;
    fin>>n>>k;
    for(int i = 0; i < n;i++)
        fin>>v[i];
    for(int i =0; i<n; i++){
        while(v[i] <= v[dq[coada]] && capat <= coada)
            coada--;
        coada++;
        dq[coada] = i;

        if(dq[capat] == i-k)
            capat++;
        if((i-k+1) >= 0)
            suma_min = suma_min + v[dq[capat]];

    }
    fout<<suma_min;
}