Cod sursa(job #2180156)

Utilizator oso.andinoooIonut Stan oso.andinooo Data 20 martie 2018 17:44:58
Problema Deque Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("deque.in");
ofstream fo("deque.out");

using i64 = long long;

const int N = 5e6 + 5;

int v[N];

deque<int> dq;
i64 ant;
int n, k;

int main() {
    fi >> n >> k;
    for (int i = 1; i <= n; ++i)
        fi >> v[i];

    for (int i = 1; i <= k; i++) {
        while(!dq.empty() && v[dq.front()] > v[i]) {
            dq.pop_front(); }
        dq.push_back(i); }
    ant = v[dq.front()];

    for (int i = k + 1; i <= n; i++) {
        if (i - dq.front() >= k)
            dq.pop_front();
        while(!dq.empty() && v[dq.front()] > v[i]) {
            dq.pop_front(); }
        dq.push_back(i);
        ant+= v[dq.front()]; }

    fo << ant;

    return 0; }