Cod sursa(job #2936969)

Utilizator CristianZizuCristian Zizu CristianZizu Data 9 noiembrie 2022 18:27:12
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda cnilc1_2-dq Marime 0.71 kb
#include <iostream>
#include <deque>
#include <fstream>

using namespace std;

ifstream f("deque.in");
ofstream g("deque.out");

deque <long long int> q1;
long long int a[5000005], n, k, s, r[5000005];

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

    long long int nr = 0;

    for (int i = 1;i <= n;i++){
        f >> a[i];
    }
    int p = 0;
    for (int i = 1;i <= n;i++){
        p++;
        while(!q1.empty() && a[q1.back()] > a[i])q1.pop_back();
        while(!q1.empty() && i - q1.front() + 1 > k)q1.pop_front();
        q1.push_back(i);
        if (!q1.empty() && p >= k){
            r[++nr] = a[q1.front()];
        }
    }
    for (int i = 1;i <= nr;i++){
        s += r[i];
    }
    g << s;
}