Advertisement
serega1112

krepost

Dec 30th, 2020
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.78 KB | None | 0 0
  1. n, k = map(int, input().split())
  2. nums = list(map(int, input().split()))
  3.  
  4.  
  5. def best_split(start, memo={}):
  6.     if start in memo:
  7.         return memo[start]
  8.     if n - start < k:
  9.         memo[start] = (0, [])
  10.         return memo[start]
  11.        
  12.     score = 0
  13.     starts = []
  14.     i = 0
  15.  
  16.     while i < k and start + i + k <= n:
  17.         pref_score = sum(nums[start+i:start+i+k]) * min(nums[start+i:start+i+k])
  18.         suf_score, suf_starts = best_split(start + k + i, memo)
  19.         if pref_score + suf_score > score:
  20.             score = pref_score + suf_score
  21.             starts = [start + i] + suf_starts
  22.         i += 1
  23.     memo[start] = (score, starts)
  24.  
  25.     return memo[start]
  26.  
  27. score, starts = best_split(0)
  28.  
  29. print(len(starts))
  30. print(' '.join([str(s+1) for s in starts]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement