Cod sursa(job #2168527)

Utilizator andreimuthMuth Andrei andreimuth Data 14 martie 2018 11:22:42
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 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.empty () && dq.back().first >= el)
            dq.pop_back ();
        dq.push_back (make_pair (el, i));
    }
    s = dq.front().first;
    for (i = i; i <= n; i++)
    {
        fin >> el;
        while (!dq.empty () && dq.back().first >= el)
            dq.pop_back ();
        dq.push_back (make_pair (el, i));
        while (i - dq.front().second == k && !dq.empty ())
        {
            dq.pop_front ();
        }
        s += dq.front().first;
    }

    fout << s;

    return 0;
}