Cod sursa(job #2816763)

Utilizator GBELOLCornel Dudau GBELOL Data 12 decembrie 2021 00:56:44
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include<bits/stdc++.h>
using namespace std;
#define io ios_base::sync_with_stdio(false);cin.tie(NULL)
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
ifstream f("data.in");
ofstream g("data.out");
int n, k;
deque<int> q;
int main() {
    io;
    f >> n >> k;
    int sum = 0;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        f >> v[i];
    for (int i = 0; i < k; i++) {
        while (!q.empty() && q.back() > v[i])
            q.pop_back();
        q.push_back(v[i]);
    }
    sum += q.front();
    for (int i = 0; i < n - k; i++) {
        if (!q.empty() && q.front() == v[i])
            q.pop_front();
        int next = v[i + k];
        while (!q.empty() && q.back() > next)
            q.pop_back();
        q.push_back(next);
        sum += q.front();
    }
    g << sum;

    return 0;
}