Cod sursa(job #1780101)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 15 octombrie 2016 20:49:07
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <deque>
#include <stack>
using namespace std;
ifstream ka("deque.in");
ofstream ki("deque.out");

struct element
{
    int val, ord;
};

deque <element> coada;
stack <element> stivatemp;

int n, k, x;
long long suma;


int main()
{
    ka >> n >> k >> x;
    element el;
    el.val = x;
    el.ord = 1;
    coada.push_back(el);
    for(int i = 2; i <= n; i++)
    {
        ka >> x;
        element elo;
        elo.val = x;
        elo.ord = i;
        while(!coada.empty() && x <= coada.back().val)
            coada.pop_back();
        coada.push_back(elo);
        if(i >= k)
        {
            while(i - coada.front().ord + 1 > k)
                coada.pop_front();
            suma += coada.front().val;
        }
    }
    ki << suma;
}