Cod sursa(job #2229677)

Utilizator Cojocaru_Andrei_CristianCojocaru Andrei Cristian Cojocaru_Andrei_Cristian Data 7 august 2018 20:48:58
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <deque>
using namespace std;
deque <int>D;
int v[5000005];
int main()
{   ifstream cin("deque.in");
    ofstream cout("deque.out");
    int 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(i-D.front()<k&&k<=i)
            {
                s+=v[D.front()];
            }
        else
            if(k<=i)
           {
               D.pop_front();
               s+=v[D.front()];
           }
    }
    cout<<s;
    return 0;
}