Cod sursa(job #1816117)

Utilizator AlexDontuAlex Dontu AlexDontu Data 26 noiembrie 2016 09:54:39
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;
ifstream fin ("deque.in");
ofstream fout ("deque.out");
long long a[500000];
deque<int> d;
int main()
{
    int i,n,k,s=0;
    fin>>n>>k;
    for (i=1; i<=n; i++)
    {
        fin>>a[i];
    }
    d.push_back(1);
    for (i=2; i<=n; i++)
    {
        while (!d.empty()&&a[d.back()]>=a[i])
        {
            if (d.size()==0) break;
            else d.pop_back();
        }
        d.push_back(i);
        if (d.back()-d.front()>=k)
        {
            d.pop_front();
        }
        if (i>=k)
        {
            s=s+a[d.front()];

        }
    }
    fout<<s;

    return 0;
}