Cod sursa(job #2943902)

Utilizator tudordaian11Daian Tudor Marius tudordaian11 Data 21 noiembrie 2022 19:35:32
Problema Deque Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin("deque.in");
ofstream cout("deque.out");

struct value
{
    int val, pos;
};
const int dim = 5e5+5;
value v[ dim ], dequeue[ dim ];

int main()
{
    int l_fr, n, st = 1, dr = 0, suma = 0;
    cin >> n >> l_fr;
    for ( int i = 1; i <= n; ++i )
    {
        cin >> v[ i ].val;
        v[ i ].pos = i;
    }
    for ( int i = 1; i <= n; ++i )
    {
        ++dr, dequeue[ dr ].val = v[ i ].val, dequeue[ dr ].pos = v[ i ].pos;
        if ( v[ st ].pos < i - l_fr + 1 )
            st++;
        for ( int j = st + 1; j <= dr; j++)
            for ( int k = j; k > st; --k )
                if ( dequeue[ j ].val < dequeue[ k - 1 ].val )
                    dequeue[ k - 1 ].val = dequeue[ j ].val;
        if ( i >= l_fr )
            suma += dequeue[ st ].val;
    }
    cout << endl << suma;
}