Cod sursa(job #2766670)

Utilizator Andrei_TudorAndrei Tudor Andrei_Tudor Data 2 august 2021 19:08:02
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 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, 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;
}