Cod sursa(job #2674414)

Utilizator pctirziuTirziu Petre pctirziu Data 19 noiembrie 2020 09:04:21
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.54 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
deque < int > deq;
int v[5000005];
int main()
{
    int i, j, n, k, a, sum=0;
    cin >> n >> k;
    for( i=1; i<=n; i++ )
    {
        cin >> v[i];
        while( !deq.empty() and v[deq.back()] >= v[i] )
            deq.pop_back();
        deq.push_back( i );
        if( deq.front() <= i-k)
            deq.pop_front();
        if( i >= k )
            sum+= v[deq.front()];
    }
    cout << sum;
    return 0;
}