Cod sursa(job #2657394)

Utilizator MoarcascosminMoarcas Cosmin Moarcascosmin Data 10 octombrie 2020 14:15:59
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
///deque-infoarena
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

ifstream f("deque.in");
ofstream g("deque.out");

int n, k, numar;
deque <pair<int, int>> D;

int main()
{
    f >> n >> k >> numar;
    int suma = 0;
    D.push_back({numar, 0});
    for(int i = 1; i < n; i++)
    {
        f >> numar;
        if(!D.empty() && i - D.front().second >= k)
            D.pop_front();
        while(!D.empty() && numar < D.back().first)
            D.pop_back();
        D.push_back({numar, i});
        if(i >= k - 1)
            suma += D.front().first;
    }
    g << suma;
    return 0;
}