Cod sursa(job #2649836)

Utilizator laraamy16Cioc Amelia laraamy16 Data 16 septembrie 2020 16:18:39
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 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, i;
    f >> N >> K;
    //
    for(i = 1; i <= K; i++)
    {
        f >> a;
        while(!D.empty() && a <= D.back().first)
            D.pop_back();
        D.push_back({a, i});
    }
    long long sMin = D.front().first;
    for(i = K + 1; i <=N; i++)
    {
        f >> a;
        while(!D.empty() && a <= D.back().first)
        D.pop_back();
        D.push_back({a, i});
        if(D.front().second == i - K)
            D.pop_front();
        sMin += D.front().first;
    }
    g<<sMin;
    return 0;
}