Cod sursa(job #2007633)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 3 august 2017 15:47:27
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

const int NLIM = 5e6 + 10;

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

int K, N;

deque< int > dq;
deque< int > idx;

int main()
{
    long long res = 0;
    fin >> N >> K;
    for( int i = 0; i < N; ++i )
    {
        int x;
        fin >> x;

        while( dq.size() && x < dq.back() )
        {
            dq.pop_back();
            idx.pop_back();
        }
        dq.push_back( x );
        idx.push_back( i );



        while( idx.front() <= i - K )
        {
            dq.pop_front();
            idx.pop_front();
        }
        if( i >= K - 1 )
        {
            res += dq.front();
            //cout << dq.front() << " ";
        }


    }
   // cout << "\n";
    fout << res;

    return 0;
}