Cod sursa(job #2842267)

Utilizator CiuiGinjoveanu Dragos Ciui Data 31 ianuarie 2022 14:45:41
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
 
ifstream fin("deque.in");
ofstream fout("deque.out");
 
const int MAX_SIZE = 5000005;
int v[MAX_SIZE], n, k;
 
int main() {
    fin >> n >> k;
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }
    deque<int> numbers;
    long long sum = 0;
    for (int i = 1; i <= n + 1; ++i) {
        if (i > k) {
            ++cnt;
            sum += numbers.front();
            numbers.pop_front();
        }
        int j = i - 1;
        while (j > cnt) {
            if (numbers[j] >= v[i]) {
                numbers[j] = v[i];
            } else {
                break;
            }
            --j;
        }
        numbers.push_back(v[i]);
    }
    fout << sum;
}
 
/*
 
 1 1
 -1 -> -1
 
 5 1
 1 2 3 4 5 -> 15
 
 9 3
 -7 9 2 4 -1 5 6 7 1 -> -2
 
 9 3
 -7 9 2 4 -1 5 6 7 10 -> 3
 
 4 4
 1 -1 2 3 -> -1
 
 
 
 */