- Define precisely what one DP state represents.
- Establish the base cases before transitions are evaluated.
- Process states in dependency order and combine only already-known values.
Code notes
- 86 lines of Python from the credited upstream file abc390_e.py.
- The implementation visibly relies on sequence storage, ordered lookup, cached states.
- No explicit loop blocks detected.
Complexity
Multiply the number of reachable states by the work performed for each transition, then include the stored state table in memory usage.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3from bisect import bisect_left4from typing import List5 6 7def bisect_ge(sorted_array: List[int], value: int):8 """Find the smallest element >= x and its index, or None if it doesn't exist."""9 10 if sorted_array[-1] >= value:11 index: int = bisect_left(sorted_array, value)12 13 return index, sorted_array[index]14 15 return None, None16 17 18def main():19 import sys20 21 input = sys.stdin.readline22 23 n, x = map(int, input().split())24 foods = [list() for _ in range(3)]25 26 for _ in range(n):27 vi, ai, ci = map(int, input().split())28 vi -= 129 foods[vi].append((ai, ci))30 31 vitamins = list()32 33 34 for food in foods:35 dp = [0 for _ in range(x + 1)]36 37 for fi in food:38 ndp = [0 for _ in range(x + 1)]39 aj, cj = fi40 41 for j in range(x + 1):42 ndp[j] = max(ndp[j], dp[j])43 nj = j + cj44 45 if nj > x:46 continue47 48 ndp[nj] = max(ndp[nj], dp[j] + aj)49 50 dp = ndp51 52 vitamins.append(dp)53 54 55 ac, wa = 0, 10**956 57 def f(wj):58 total = 059 60 for i in range(3):61 if vitamins[i][x] < wj:62 return False63 64 j, _ = bisect_ge(vitamins[i], wj)65 66 if j is None:67 return False68 69 total += j70 71 return total <= x72 73 while abs(wa - ac) > 1:74 wj = (ac + wa) 275 76 if f(wj):77 ac = wj78 else:79 wa = wj80 81 print(ac)82 83 84if __name__ == "__main__":85 main()86