Cod sursa(job #2642155)

Utilizator Ionut2791Voicila Ionut Marius Ionut2791 Data 13 august 2020 20:05:44
Problema Deque Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <deque>
#include <utility>
using namespace std;

deque <pair<int,int> > deck;
long long sum = 0, i = 1, nr;
int n, k;

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

    fin >> n >> k;

    for(i = 1; i < k; ++i){
        fin >> nr;

        deck.push_front(make_pair(nr, i));
    }

    for(; i <= n; ++i){
        fin >> nr;

        if(nr <= deck.back().first){
            deck.clear();
        }
        else{
            while(nr <= deck.front().first){
                deck.pop_front();
            }
        }
        deck.push_front(make_pair(nr, i));

        if(deck.back().second <= i-k)
            deck.pop_back();

        sum += deck.back().first;
    }
    fout << sum ;
    return 0;
}