Cod sursa(job #3269056)

Utilizator justy41Babiciu Iustin justy41 Data 18 ianuarie 2025 10:39:32
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.56 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");

deque<long long> dq; int v[5000006];
long long K, N, min_sum = 0;

int main()
{
    fin>>N>>K;
    for(int i = 1; i<=N; i++)
        fin>>v[i];
    dq.push_back(1);

    for(int i = 2; i<=N; i++)
    {
        while(!dq.empty() && v[i] <= v[dq.back()])
            dq.pop_back();

        dq.push_back(i);

        if (i - dq.front() == K) dq.pop_front();
        if (i >= K) min_sum += v[dq.front()];
    }

    fout<<min_sum;

    return 0;
}