Cod sursa(job #2168584)

Utilizator andreimuthMuth Andrei andreimuth Data 14 martie 2018 11:37:18
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 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 >> 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 (!dq.empty () && i - dq.front().second == k)
            dq.pop_front ();
        s += dq.front().first;
    }
    fout << s;
    return 0;
}