Cod sursa(job #3158769)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 19 octombrie 2023 19:10:16
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
//https://infoarena.ro/problema/deque
#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    int n,i,x,k;
    long long sum=0;
    deque <pair<int,int>> dq;
    fin>>n>>k;
    fin>>x;
    dq.emplace_back(0,x);
    for(i=1;i<n;i++)
    {
        fin>>x;
        if(dq.empty()==0)
        {
            while(x<dq.back().second&&dq.empty()==0)
            {
                dq.pop_back();
            }
        }

        dq.emplace_back(i,x);

        if(i>=(k-1))
        {
            while(dq.front().first<=(i-k)&&dq.empty()==0)
            {
                dq.pop_front();
            }
            //cout<<dq.front().second<<"\n";
            if(dq.empty()==0)
            {
                sum+=(long long)dq.front().second;
            }
        }

    }
//    cout<<dq.front().second<<"\n";
//    sum+=(long long)dq.front().second;
    //return 0;
//    for(auto &x : dq)
//    {
//        cout<<x.first<<" "<<x.second<<"\n";
//    }
    fout<<sum;
    return 0;
}