Cod sursa(job #2766202)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 31 iulie 2021 12:51:49
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <deque>
#define st first
#define dr second

using namespace std;

ifstream fin  ("deque.in");
ofstream fout ("deque.out");

deque < pair<int, int> > q;
int n, k, x;
long long sol;

int main (){
    fin>>n>>k>>x;
    if(k == 1){
        sol+=x;
        for(int i=2; i<=n; i++){
            fin>>x;
            sol += x;
        }
        fout<<sol;
    }else{
        q.push_back({x, 1});
        for(int i=2; i<=n; i++){
            fin>>x;
            while(!q.empty() && x < q.back().st)
                q.pop_back();
            q.push_back({x, i});

            if(i >= k){
                if(i - q.front().dr == k)
                    q.pop_front();
                sol += q.front().st;
            }
        }
        fout<<sol;
    }



    return 0;
}