Cod sursa(job #2943921)

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

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

const int dim = 5e5+5;
int 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 ];
    }
    for ( int i = 1; i <= n; ++i )
    {
        while ( st <= dr && v[ i ] < v[ dequeue[ dr ] ] )
            --dr;
        dequeue[ ++dr ] = i;
        if ( dequeue[ st ] = i - l_fr )
            st++;
        if ( i >= l_fr )
            suma += v[ dequeue[ st ] ] ;
    }
    cout << suma;
}