Cod sursa(job #2842396)

Utilizator StefanL2005Stefan Leustean StefanL2005 Data 31 ianuarie 2022 18:47:23
Problema Deque Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <vector>
#include <deque>
#include <fstream>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");

bool verify(int i, int k, vector<int64_t> v, int64_t A)
{
    for (int j = i; j > i - k + 1; j--)
        if (v[j] == A)
            return false;
    return true;
}
int main()
{
    int n, k, nr = 0;
    int64_t sum = 0;
    in>> n >> k;

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

    deque<int64_t> dQ;
    dQ.push_front(v[0]);
    nr++;
    if (k == 1)
    {
        sum += dQ.front();
        dQ.pop_front();
        nr--;
    }

    for (int i = 1; i < n; i++)
    {
        nr++;
        if (dQ.empty() || v[i] > dQ.front())
            dQ.push_front(v[i]);
        else
        {
            while (not dQ.empty() && v[i] <= dQ.front())
            {
                dQ.pop_front();
            }
            dQ.push_front(v[i]);
        }


        if (nr == k)
        {
            sum += dQ.back();
            if (verify(i, k, v, dQ.back()))
                dQ.pop_back();
            nr--;
        }
    }
    out<< sum;


    in.close();
    out.close();
    return 0;
}