Cod sursa(job #2766671)

Utilizator Andrei_TudorAndrei Tudor Andrei_Tudor Data 2 august 2021 19:09:17
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <queue>
using namespace std;
deque <pair <int, int>> q;
ifstream cin("deque.in");
ofstream cout("deque.out");
int main()
{
    int n, k, nr;
    long long s = 0;
    cin >> n >> k >> nr;
    q.push_back({nr, 1});
    /*
    cout << "Deque Pas 1: ";
    for(auto elem : q){
        cout << elem.first << " ";
    }
    cout << "\n";
    */
    for(int i = 2; i <= n; i ++){
        cin >> nr;
        while(!q.empty() && q.back().first > nr){
            q.pop_back();
        }
        q.push_back({nr, i});
        /*
        cout << "Deque Pas " << i << ": ";
        for(auto elem : q){
            cout << elem.first << " ";
        }
        cout << "\n";
        */
        if(i >= k){
            if(i - q.front().second >= k){
                q.pop_front();
            }
            s += q.front().first;
        }
        /*
        cout << "Minimul este: " << q.front().first << "\n";
        cout << "Suma este: " << s << "\n";
        cout << "\n";
        */
    }
    cout << s;
    return 0;
}