結果
問題 |
No.1606 Stuffed Animals Keeper
|
ユーザー |
![]() |
提出日時 | 2023-04-04 08:58:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 589 ms / 3,000 ms |
コード長 | 675 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 81,712 KB |
実行使用メモリ | 80,000 KB |
最終ジャッジ日時 | 2024-09-25 10:40:08 |
合計ジャッジ時間 | 9,648 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
N = int(input()) A = list(map(int, input().split())) X, Y = [], [] cntX, cntY = 0, 0 for a in A: if a == 2: X.append(cntX) Y.append(cntY) cntX, cntY = 0, 0 elif a == 0: cntX += 1 else: cntY += 1 X.append(cntX) Y.append(cntY) M = len(X) geta = 5005 inf = 10 ** 18 pre = [inf] * (2 * geta) pre[geta] = 0 for i in range(M): dp = [inf] * (2 * geta) for j in range(2 * geta): if j + X[i] < 2 * geta: dp[j + X[i]] = min(dp[j + X[i]], pre[j] + X[i]) if j - Y[i] >= 0: dp[j - Y[i]] = min(dp[j - Y[i]], pre[j]) dp, pre = pre, dp print(pre[geta]) if pre[geta] < inf else print(-1)