Cod sursa(job #2558792)

Utilizator hudisteanumihaelaHudisteanu Mihaela hudisteanumihaela Data 26 februarie 2020 20:00:50
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.54 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("deque.in");
ofstream fout ("deque.out");
deque <pair<int, int>> deq;
long long n,k,x,s,i;
int main()
{
    fin>>n>>k;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        while(!deq.empty() && deq.back().first>x)
            deq.pop_back();
        deq.push_back({x, i});
        if(i>=k)
        {
            while(!deq.empty() && deq.front().second<=i-k)
                deq.pop_front();
            s+=deq.front().first;
        }
    }
    fout<<s;
    return 0;
}