Cod sursa(job #2775815)

Utilizator radu.z5Zamfirescu Radu Ioan radu.z5 Data 17 septembrie 2021 13:00:01
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <list>

using namespace std;

long deque(const int *v, const int n, const int k) {
    long sum = 0L;
    list<int> deq;
    int i;

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

    sum += v[deq.front()];
    if (deq.front() == 0)
        deq.pop_front();

    while (i < n) {
        while (!deq.empty() && v[deq.back()] >= v[i])
            deq.pop_back();
        deq.push_back(i);
        sum += v[deq.front()];
        if (deq.front() == i - k + 1)
            deq.pop_front();
        i++;
    }
    return sum;
}

int main(void) {
    ifstream in("deque.in");
    ofstream out("deque.out");
    int n, k;
    in >> n >> k;

    int *v = new int[n];
    for (int i = 0; i < n; i++)
        in >> v[i];

    out << deque(v, n, k);

    delete[] v;
    in.close();
    out.close();
    return 0;
}