Cod sursa(job #2742098)

Utilizator Tudor_StefanaStefana Tudor Tudor_Stefana Data 20 aprilie 2021 09:19:58
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("deque.in");
ofstream g("deque.out");

deque < pair < long long , long long > > d;
long long n,k,i,x,s;

int main()
{
    f>>n>>k;
    for(i=1;i<=k;i++)
    {
        f>>x;
        while(!d.empty() && x<d.back().second)d.pop_back();
        d.push_back({i,x});
    }
    s=d.front().second;

    for(i=k+1;i<=n;i++)
    {
        f>>x;
        while(!d.empty() && x<d.back().second)d.pop_back();
        d.push_back({i,x});
        while(d.front().first<=i-k)d.pop_front();
        s+=d.front().second;
    }
    g<<s;
    return 0;
}