Cod sursa(job #2842334)

Utilizator StefanL2005Stefan Leustean StefanL2005 Data 31 ianuarie 2022 17:06:12
Problema Deque Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 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]);
    nr++;
    cop = dQ.front();
    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();
                 c = 0;
                 if (i < n - 1)
                    cop = v[i + 1];
            }
            nr--;
        }
    }
    out<< sum;

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