Cod sursa(job #2652791)

Utilizator AndreiAlexandru2k3Ciucan Andrei Alexandru AndreiAlexandru2k3 Data 25 septembrie 2020 18:42:50
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

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

deque<pair<int,int>>D;

int main()
{
    int N,K,a;
    f>>N>>K;
    long long sMin=0;
    for(int i=1;i<=N;i++)
    {
        f>>a;
        while(!D.empty()&&a<=D.back().first)
            D.pop_back();
        D.push_back({a,i});
        if(i>=K)
        {
            if(D.front().second==i-K)
                D.pop_front();
            sMin+=D.front().first;
        }
    }
    g<<sMin;
    f.close();
    g.close();
    return 0;
}