Cod sursa(job #2842294)

Utilizator StefanL2005Stefan Leustean StefanL2005 Data 31 ianuarie 2022 15:24:58
Problema Deque Scor 10
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");

int main()
{
    int n, k, sum = 0, nr = 0, c = 1, cop;
    in>> n >> k;

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

    deque<int> dQ;
    dQ.push_front(v[0]);
    cop = v[0];
    nr++;

    if (nr == k)
    {
        sum += dQ.back();
        if (c == k)
        {
            dQ.pop_back();
        }
        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 (cop == dQ.back())
            c++;
        else
        {
            cop = dQ.back();
            c = 1;
        }

        if (nr == k)
        {
            sum += dQ.back();
            if (c == k)
                dQ.pop_back();

            nr--;
        }
    }
    out<< sum;

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