結果
問題 |
No.1606 Stuffed Animals Keeper
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:20:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 231 ms / 3,000 ms |
コード長 | 1,530 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 82,704 KB |
実行使用メモリ | 78,684 KB |
最終ジャッジ日時 | 2025-03-20 20:21:08 |
合計ジャッジ時間 | 6,571 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
n = int(input()) A = list(map(int, input().split())) pos = [i for i in range(n) if A[i] != 2] n0 = A.count(0) n1 = A.count(1) if not pos: print(0) exit() groups = [] current_group = [pos[0]] for p in pos[1:]: if p == current_group[-1] + 1: current_group.append(p) else: groups.append(current_group) current_group = [p] groups.append(current_group) group_info = [] for group in groups: cnt0 = 0 cnt1 = 0 for idx in group: if A[idx] == 0: cnt0 += 1 else: cnt1 += 1 group_len = len(group) group_info.append((group_len, cnt1, cnt0)) # cost0 is cnt1, cost1 is cnt0 target_sum = n0 current_dp = {0: 0} for glen, cost0, cost1 in group_info: new_dp = {} for s in current_dp: current_cost = current_dp[s] # Option 1: assign to 0 new_s = s + glen if new_s <= target_sum: if new_s in new_dp: if current_cost + cost0 < new_dp[new_s]: new_dp[new_s] = current_cost + cost0 else: new_dp[new_s] = current_cost + cost0 # Option 2: assign to 1 new_s_1 = s new_cost_1 = current_cost + cost1 if new_s_1 in new_dp: if new_cost_1 < new_dp[new_s_1]: new_dp[new_s_1] = new_cost_1 else: new_dp[new_s_1] = new_cost_1 current_dp = new_dp if target_sum in current_dp: min_cost = current_dp[target_sum] print(min_cost // 2) else: print(-1)