Cod sursa(job #2802161)

Utilizator TeodorMarciucMarciuc Teodor TeodorMarciuc Data 17 noiembrie 2021 17:42:20
Problema Deque Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
deque<int>D;
int n, k, s, i, j, v[1005];
int main()
{
    ifstream cin("deque.in");
    ofstream cout("deque.out");
    cin >> n;
    cin >> k;
    cin >> v[1];
    D.push_back(1);
    for (i = 2;i <= k;i++) {
        cin >> v[i];
        if (D.empty() == 0 and v[i] >= v[D.back()])
            D.push_back(i);
        else {
            while (D.empty() == 0 and v[i] < v[D.back()])
                D.pop_back();
            D.push_back(i);
        }
    }
    s = v[D.front()];
    for (i = k + 1;i <= n;i++) {
        cin >> v[i];
        if (D.empty() == 0 and v[i] >= v[D.back()])
            D.push_back(i);
        else {
            while (D.empty() == 0 and v[i] < v[D.back()])
                D.pop_back();
            D.push_back(i);
        }
        while (i - k + 1 > D.front())
            D.pop_front();
        s += v[D.front()];
    }
    cout << s;
}