1
# Runtime: 760 ms (Top 68.15%) | Memory: 14.5 MB (Top 56.05%)
2

3

4
class Solution:
5
    def tallestBillboard(self, rods: List[int]) -> int:
6
        dp = collections.defaultdict(int)
7
        dp[0] = 0
8
        for x in rods:
9
            nxt = dp.copy()
10
            for d, y in dp.items():
11
                # init state
12
                # ------|----- d -----| # tall side
13
                # - y --| # low side
14

15
                # put x to tall side
16
                # ------|----- d -----|---- x --|
17
                # - y --|
18
                nxt[d + x] = max(nxt.get(x + d, 0), y)
19

20
                nxt[abs(d - x)] = max(nxt.get(abs(d - x), 0), y + min(d, x))
21
            dp = nxt
22
        return dp[0]