Cod sursa(job #2735895)

Utilizator Mihai7218Bratu Mihai-Alexandru Mihai7218 Data 2 aprilie 2021 22:21:48
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
long long n, a, mn, imn, i, k, s;
queue<int> Q, Qb;
int main()
{
    fin >> n >> k; mn = int(1e7)+1;
    Q.push(0);
    for (i = 1; i < k;  i++)
    {
        fin >> a;
        if (a < mn) mn = a, imn = i;
        Q.push(a);
    }
    for (i = k; i <= n; i++)
    {
        fin >> a;
        Q.push(a);
        Q.pop();
        if (a < mn) mn = a, imn = i;
        else if (i - imn >= k)
        {
            mn = int(1e7)+1;
            while (!Q.empty())
            {
                if (Q.front() < mn) mn = Q.front();
                Qb.push(Q.front());
                Q.pop();
            }
            while(!Qb.empty())
            {
                Q.push(Qb.front());
                Qb.pop();
            }
        }
        s+= mn;
    }
    fout << s;
    return 0;
}