結果

問題 No.1606 Stuffed Animals Keeper
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0