Cod sursa(job #3271256)

Utilizator BucsMateMate Bucs BucsMate Data 25 ianuarie 2025 15:24:13
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 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.back().second - sor.front().second >= K){
            sor.pop_front();
        }
        for(int i = sor.size()-2; i >= 0 && sor[i].first >= sor.back().first; i--){
            if(sor[i].first >= sor.back().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
*/