Pagini recente » Cod sursa (job #2881513) | Cod sursa (job #544663) | Cod sursa (job #125701) | Cod sursa (job #1572588) | Cod sursa (job #2535847)
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))