Cod sursa(job #3239887)

Utilizator nicushor21Pirlog Marian Nicolae nicushor21 Data 8 august 2024 16:41:51
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
long long n,k,i,sol,x;
deque <pair<long long,long long>> v;
int main()
{
    fin>>n>>k;
    for(i=1;i<k;i++){
        fin>>x;
        while(!v.empty() && v.back().first >= x)
            v.pop_back();
        v.push_back(make_pair(x,i));
    }
    for(i=k;i<=n;i++){
        fin>>x;
        while(!v.empty() && v.back().first >= x)
            v.pop_back();
        v.push_back(make_pair(x,i));
        while(!v.empty() && v.front().second < i-k+1)
            v.pop_front();
        sol += v.front().first;
    }
    fout<<sol;
    return 0;
}