Cod sursa(job #2168556)

Utilizator andreimuthMuth Andrei andreimuth Data 14 martie 2018 11:30:31
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <deque>
#define nmax 5 000 001
using namespace std;
ifstream fin ("deque.in");
ofstream fout ("deque.out");
deque < pair <int, int> > dq;

int el, n, k, i, s, j, minn;
int main ()
{
    fin >> n >> k;
    fin >> el;
    dq.push_back (make_pair (el, 1));
    for (i = 2; i <= k; i++)
    {
        fin >> el;
        while (dq.back().first >= el && dq.size ())
            dq.pop_back ();
        dq.push_back (make_pair (el, i));
    }
    s = dq.front().first;
    for (i = i; i <= n; i++)
    {
        fin >> el;
        while (dq.back().first >= el && dq.size ())
            dq.pop_back ();
        dq.push_back (make_pair (el, i));
        while (i - dq.front().second == k && dq.size ())
        {
            dq.pop_front ();
        }
        s += dq.front().first;
    }
    fout << s;

    return 0;
}