Cod sursa(job #2974235)

Utilizator zarg169Roxana zarg169 Data 3 februarie 2023 16:30:18
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
//https://www.infoarena.ro/problema/deque
#include <fstream>
#include <deque>

using namespace std;

deque <pair<int, int>> myDeque;
int array[5000005];

int main()
{
    ifstream fin("deque.in");
    ofstream fout("deque.out");
    int N, K, sum = 0;
    pair<int, int> value;

    fin >> N >> K;

    for (int i = 1; i <= N; ++i) {
        fin >> array[i];
        value.first = i;
        value.second = array[i];
        if (myDeque.empty()) {
            myDeque.push_back(value);
        } else {
            while (array[i] <= myDeque.back().second) {
                myDeque.pop_back();
            }
            myDeque.push_back(value);
            while (myDeque.front().first <= i - K) {
                myDeque.pop_front();
            }
            if (i >= K) {
                sum += myDeque.front().second;
            }
        }
    }

    fout << sum;

}