Cod sursa(job #2420123)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 10 mai 2019 17:54:12
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 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;
    long long minSum = 0;
    deque<pair<int, int>> nums;
    fin>>N>>K;

    while(++n <= N)
    {
        fin>>inNum;

        while(!nums.empty() && 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;
}