Cod sursa(job #2229683)

Utilizator Cojocaru_Andrei_CristianCojocaru Andrei Cristian Cojocaru_Andrei_Cristian Data 7 august 2018 20:56:34
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <deque>
using namespace std;
deque <int>D;
int v[5000005];
int main()
{   ifstream cin("deque.in");
    ofstream cout("deque.out");
    long long n,k,s=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    D.push_back(1);
    for(int i=2;i<=n;i++)
    {
        while(!D.empty())
        {
            if(v[D.back()]>=v[i])
                D.pop_back();
            else
                break;
        }
        D.push_back(i);
        if(D.front()==i-k)
            {
                D.pop_front();
            }
        if(k<=i)
           {
               s+=v[D.front()];
           }
    }
    cout<<s;
    return 0;
}