Cod sursa(job #2851598)

Utilizator MerlinTheWizardMelvin Abibula MerlinTheWizard Data 18 februarie 2022 20:54:10
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include<iostream>
#include<fstream>
#include<deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
deque<int> q;
int n,k;
int v[50000001];
void Citire()
{
    f>>n>>k;
}
void Solve()
{
    for(int i=1;i<=n;i++)
        f>>v[i];
    int suma=0;
    for(int i=1;i<=n;i++)
    {
        while(!q.empty() && v[q.back()]>=v[i])
             q.pop_back();
        q.push_back(i);
        if(q.back()-q.front()>=k)
            q.pop_front();
        if(i>=k)
        {
            if(!q.empty())
                suma=suma+v[q.front()];
        }
    }
    g<<suma;
}
int main()
{
    Citire();
    Solve();
}