Cod sursa(job #2561289)

Utilizator tudorcioc5Cioc Tudor tudorcioc5 Data 28 februarie 2020 18:31:21
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>


using namespace std;


vector <int> numbers (5000003);
int N,K, i, sum;


ifstream fin;
ofstream fout;


int main(void){
    deque <int> Deque;

    fin.open("deque.in");
    fin>>N>>K;
    for (i=1; i<=N; i++)
        fin>>numbers[i];
    fin.close();

    Deque.push_front(1);

    for (i=2; i<K; i++){
        while (numbers[Deque.front()] >= numbers[i] && Deque.size() > 0) Deque.pop_front();
        Deque.push_front(i);
    }




    for (i=K; i<=N; i++){
        while (numbers[Deque.front()] >= numbers[i] && Deque.size() > 0) Deque.pop_front();
        Deque.push_front(i);
        sum += numbers[Deque.back()];

        if (Deque.back() == i - K + 1 ) Deque.pop_back();
    }

    fout.open("deque.out");
    fout<<sum<<"\n";
    fout.close();

    return 0;
}