Cod sursa(job #3248894)

Utilizator BucsMateMate Bucs BucsMate Data 13 octombrie 2024 17:55:11
Problema Deque Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

ifstream input("deque.in");
ofstream output("deque.out");

int main()
{
    deque<pair<int, int>> sor;
    int N, K;
    input >> N >> K;

    int x;
    long long s = 0;
    for(int i = 0; i < N; i++){
        input >> x;
        sor.push_back({x, i});
        if(sor[sor.size()-1].second - sor[0].second >= K){
            sor.pop_front();
        }
        for(int i = sor.size()-2; i >= 0; i--){
            if(sor[i].first >= sor[sor.size()-1].first){
                sor.erase(sor.begin() + i);
            }
        }
        if(i >= K-1){
            s += sor.front().first;
        }/*
        for(auto it = sor.begin(); it != sor.end(); it++){
            cout << (*it).first << " " << (*it).second << "; ";
        }
        cout << endl;*/
    }
    output << s;
    return 0;
}

/*
9 3

-7 9 2 4 -1 5 6 7 1

-7 2 -1 -1 -1 5 1

-1 5 6
*/