Cod sursa(job #2183079)

Utilizator AndreiSorin26012001Cirpici Andrei Sorin AndreiSorin26012001 Data 22 martie 2018 19:58:50
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, k;
long long s;
int arr[5000005];
deque< int > v;

int main()
{
    in>>n>>k;
    for( int i = 1; i <= n; i++ )
        in>>arr[i];

    for( int i = 1; i <= n; i++ )
    {
        while( !v.empty() && arr[ v.back() ] > arr[i] )
            v.pop_back();

        v.push_back(i);

        if( v.front() <= i - k )
            v.pop_front();

        if( i >= k )
            s += arr[ v.front() ];
    }

    out<<s;

    return 0;
}