Cod sursa(job #2535847)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 1 februarie 2020 11:58:16
Problema Deque Scor 30
Compilator py Status done
Runda Arhiva educationala Marime 0.74 kb
from collections import deque

def read_gen(fname):
    with open(fname, 'rt') as fin:
        for line in fin:
            for val in line.split():
                yield int(val)

def insert_last(dq, index, x):
    while len(dq) > 0 and dq[-1][1] >= x:
        dq.pop()
    dq.append((index, x))

def remove_first(dq, index):
    if len(dq) > 0 and index - dq[0][0] + 1 > k:
        dq.popleft()
    

if __name__ == "__main__":

    it = read_gen('deque.in')
    n, k = next(it), next(it)
    dq = deque()
    ss = 0

    for i in range(n):
        x = next(it)
        remove_first(dq, i)
        insert_last(dq, i, x)
        if i >= k - 1:
            ss += dq[0][1]

    with open('deque.out', 'wt') as fout:
        fout.write('{}\n'.format(ss))