fedor-resh

Untitled

Sep 2nd, 2023
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.41 KB | None | 0 0
  1. n = int(input())
  2. arr = [0]+list(map(int, input().split()))
  3. n+=1
  4. mi, ma = map(int, input().split())
  5. dp = [0]*(n)
  6. from collections import deque
  7. stack = deque()
  8. for i in range(mi, n):
  9.     while stack and stack[-1] < dp[i-mi]:
  10.         stack.pop()
  11.     stack.append(dp[i-mi])
  12.     if i >= ma:
  13.         if stack and stack[0] == dp[i-ma]:
  14.             stack.popleft()
  15.     dp[i] = stack[0]+arr[i]
  16.  
  17. print(dp[-1] or -1)
Advertisement
Add Comment
Please, Sign In to add comment