Cod sursa(job #2420121)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 10 mai 2019 17:46:12
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int main()
{
    int N, K, inNum, n = 0, minSum = 0;
    deque<pair<int, int>> nums;
    fin>>N>>K;

    while(++n <= N)
    {
        fin>>inNum;
        if(nums.empty() || nums.back().first <= inNum)
        {
            nums.push_back({inNum, n});
        }
        else
        {
            while(nums.back().first > inNum)
            {
                nums.pop_back();
            }
            nums.push_back({inNum, n});
        }
        if(n - nums.front().second >= K)
        {
            nums.pop_front();
        }
        if(n >= K)
        {
            minSum += nums.front().first;
        }
        //cout<<nums.front().first<<", "<<nums.front().second<<"\n";
    }
    fout<<minSum;
    return 0;
}