Cod sursa(job #2018178)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 3 septembrie 2017 19:00:49
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <iostream>
#include <fstream>

using namespace std;

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

long long int n,k,i,v[5000001],deq[5000001],stanga,dreapta,sum;

int main()
{
    fin >> n >> k;
    stanga=1;
    for(i=1;i<=n;i++)
    {
        fin >> v[i];
        while(stanga<=dreapta and v[i]<=v[deq[dreapta]])
        {
            dreapta--;
        }
        dreapta++;
        deq[dreapta]=i;
        if(deq[stanga]==i-k)
        {
            stanga++;
        }
        if(i>=k)
        {
            sum+=v[deq[stanga]];
        }
    }
    fout << sum;
    return 0;
}