Cod sursa(job #2229675)

Utilizator Cojocaru_Andrei_CristianCojocaru Andrei Cristian Cojocaru_Andrei_Cristian Data 7 august 2018 20:40:40
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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++)
    {
        if(v[i]<=v[D.front()])
            {
                D.pop_front();
                D.push_front(i);
            }
        else
        {   while(1)
        {
            if(v[D.back()]>v[i])
            {D.pop_back();}
            else
            {
                D.push_back(i);
                break;
            }
        }
        }
        if(i-D.front()<k&&k<=i)
            {
                s+=v[D.front()];
            }
        else
            if(k<=i)
           {   while(1)
           {
               if(i-D.front()>=k)
                   D.pop_front();
               else
                   break;
            }
               s+=v[D.front()];
           }
    }
    cout<<s;
    return 0;
}