Cod sursa(job #2657224)

Utilizator MaraPMara P MaraP Data 10 octombrie 2020 09:51:21
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

deque<pair<int, int> > D;
int n, k;

void citire()
{
    fin>>n>>k;
    int x, sumaMinima=0;
    for(int i=0;i<n;i++)
    {
        if(!D.empty()&&i-D.front().second>=k)
            D.pop_front();
        fin>>x;
        if(D.empty()||!D.empty()&&x>D.back().first)
            D.push_back({x,i});
        else
        {
            while(x<D.back().first&&!D.empty())
                D.pop_back();
            D.push_back({x,i});
        }
        if(i>=k-1)
            sumaMinima+=D.front().first;
    }
    cout<<sumaMinima;
}
int main()
{
    citire();
    return 0;
}