Cod sursa(job #3275658)

Utilizator mateilupuMatei Lupu mateilupu Data 11 februarie 2025 14:11:41
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>

using namespace std;

int coada[5000001], v[5000001];

int main()
{
    ifstream cin ("deque.in");
    ofstream cout ("deque.out");
    int n, k, s = 0, i, inc = 1, sf = 0;
    cin >> n >> k;
    for(i = 1; i < k; i++) {
        cin >> v[i];
        while(inc <= sf && v[i] < v[coada[sf]])
            sf--;
        sf++;
        coada[sf] = i;
    }
    for(; i <= n; i++) {
        cin >> v[i];
        while(inc <= sf && v[i] < v[coada[sf]])
            sf--;
        sf++;
        coada[sf] = i;
        if(i - coada[inc] + 1 > k) {
            inc++;
        }
        s += v[coada[inc]];
    }
    cout << s;
    return 0;
}