Cod sursa(job #2883945)

Utilizator T1raduTaerel Radu Nicolae T1radu Data 2 aprilie 2022 00:01:35
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int n,k;
long long x;
deque< pair<long long,int> > deq;
int main()
{
    fin >> n >> k;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        fin >> x;
        while(!deq.empty() && x<=deq.back().first)
            deq.pop_back();
        deq.push_back(make_pair(x,i));
        if(i>=k)
        {
            while(i-deq.front().second>=k) deq.pop_front();
            sum+=deq.front().first;
        }
    }
    fout << sum;
    return 0;
}