結果
問題 |
No.1606 Stuffed Animals Keeper
|
ユーザー |
|
提出日時 | 2023-03-02 00:21:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 521 ms / 3,000 ms |
コード長 | 1,046 bytes |
コンパイル時間 | 340 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 274,140 KB |
最終ジャッジ日時 | 2024-09-16 21:28:35 |
合計ジャッジ時間 | 7,620 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
def oi(): return int(input()) def os(): return input() def mi(): return list(map(int, input().split())) # import sys # input = sys.stdin.readline # import sys # sys.setrecursionlimit(10**8) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') input_count = 0 N = oi() A = mi() elements = [] temp = {0:0, 1:0} for a in A: if a == 2: if len(temp)!=0: elements.append(temp) temp = {0:0, 1:0} else: temp[a] += 1 if len(temp)!=0: elements.append(temp) one_sum = A.count(1) diffs = [] for e in elements: diffs.append([e[0] + e[1], e[0]]) # 一致してなければDP INF = 10**5 dp = [[INF] * (N+2) for _ in range(len(elements)+1)] dp[0][0] = 0 for y,d in enumerate(diffs): for x in range(0, N+2): dp[y+1][x] = min(dp[y][x], dp[y+1][x]) if dp[y][x] != INF: if 0 <= x+d[0] <= 2*N+1: dp[y+1][x+d[0]] = min(dp[y+1][x+d[0]], dp[y][x]+d[1]) ret = dp[-1][one_sum] if ret != INF: print(ret) else: print(-1)