Cod sursa(job #2649831)

Utilizator ChunkylappSafety reason Chunkylapp Data 16 septembrie 2020 16:15:59
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#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;
}