Cod sursa(job #2836746)

Utilizator ILikeitN Stef ILikeit Data 20 ianuarie 2022 20:45:48
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#define __USE_FILES__
#ifdef __USE_FILES__
#include <fstream>
std::ifstream in("deque.in");
std::ofstream out("deque.out");
#else
#include <iostream>
std::istream& in = std::cin;
std::ostream& out = std::cout;
#endif

// directive preprocesate
#include <algorithm>
#include <array>
#include <cassert>
#include <deque>
#include <functional>
#include <limits>
#include <math.h>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
using ll = int;

struct numar {
    ll val;
    ll index;

    numar(ll v = 0, ll i = 0)
    {
        val = v;
        index = i;
    }
};

// declaratie functii
void addToQue(std::deque<numar>& qq, numar el)
{
    // this is a special add operation
    while (!qq.empty() && qq.back().val > el.val) {
        qq.pop_back();
    }
    qq.push_back(el);
}

void printQue(std::deque<numar>& qq)
{
    for (auto&& x : qq)
        out << x.val << " ";
    out << "\n";
    return;
}

// declaratii variablile
ll n, k, sum = 0;
std::deque<numar> q;

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

    for (ll i = 1; i <= k; ++i) {
        ll v;
        in >> v;
        addToQue(q, { v, i });
        // printQue(q);
    }
    ll sum = q.front().val;

    for (ll i = k + 1; i <= n; ++i) {
        ll v;
        in >> v;
        addToQue(q, { v, i });
        while (!q.empty() && i - q.front().index >= k) {
            q.pop_front();
        }
        // printQue(q);
        sum += q.front().val; // q.front() este minimul intervalului curent
    }

    out << sum;

    return 0;
}