Cod sursa(job #2795227)

Utilizator guzgandemunteIonescu Laura guzgandemunte Data 6 noiembrie 2021 09:58:32
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <deque>
#define NMAX 5000000

using namespace std;

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

int n, k, x;
int v[NMAX];
deque <int> q;
long long sumMin;

int main()
{
    fin >> n >> k;

    for (int i = 0; i < n; ++i) fin >> v[i];

    for (int i = 0; i < k; ++i) {
        while (!q.empty() && v[q.back()] >= v[i]) q.pop_back();
        q.push_back(i);
    }

    sumMin += v[q.front()];

    for (int i = k; i < n; ++i) {
        if (i - k == q.front()) q.pop_front();
        while (!q.empty() && v[q.back()] >= v[i]) q.pop_back();
        q.push_back(i);
        sumMin += v[q.front()];
    }

    fout << sumMin;

    fin.close();
    fout.close();
    return 0;
}