Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- n, k = map(int, input().split())
- nums = list(map(int, input().split()))
- def best_split(start, memo={}):
- if start in memo:
- return memo[start]
- if n - start < k:
- memo[start] = (0, [])
- return memo[start]
- score = 0
- starts = []
- i = 0
- while i < k and start + i + k <= n:
- pref_score = sum(nums[start+i:start+i+k]) * min(nums[start+i:start+i+k])
- suf_score, suf_starts = best_split(start + k + i, memo)
- if pref_score + suf_score > score:
- score = pref_score + suf_score
- starts = [start + i] + suf_starts
- i += 1
- memo[start] = (score, starts)
- return memo[start]
- score, starts = best_split(0)
- print(len(starts))
- print(' '.join([str(s+1) for s in starts]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement