Cod sursa(job #2469072)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 6 octombrie 2019 14:53:45
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream fin ("deque.in");
ofstream fout ("deque.out");

struct A
{
    long long val;
    int poz;
};

deque < A > a;

int main()
{
    int n, k, i;
    long long x, s = 0;

    fin >> n >> k;

    for ( i = 1 ; i < k ; i++ )
    {
        fin >> x;
        if ( a.empty() == 0 ) while ( x <= a.back().val || a.empty() != 0 ) a.pop_back();
        a.push_back ( { x, i } );
    }

    for ( i = k ; i <= n ; i++ )
    {
        fin >> x;
        while ( x <= a.back().val ) a.pop_back();
        a.push_back ( { x, i } );

        while ( a.front().poz <= i-k ) a.pop_front();

        s += a.front().val;
    }

    fout << s;

    return 0;
}