結果

問題 No.3114 0→1
コンテスト
ユーザー Aldric Liew
提出日時 2025-04-20 13:44:45
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,621 bytes
コンパイル時間 566 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 18,556 KB
最終ジャッジ日時 2025-04-20 13:44:52
合計ジャッジ時間 7,042 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
s = input().strip()

from collections import defaultdict

# We'll track the current balance and the minimal balance encountered so far.
# The state is (current_balance, min_balance), and we keep the minimal flips for each state.
dp = defaultdict(lambda: float('inf'))
dp[(0, 0)] = 0  # Initial state: balance 0, min_balance 0, flips 0

for char in s:
    new_dp = defaultdict(lambda: float('inf'))
    for (current_balance, min_balance), flips in dp.items():
        if char == '1':
            new_balance = current_balance + 1
            new_min = min(min_balance, new_balance)
            if new_balance >= min_balance:
                if new_dp[(new_balance, new_min)] > flips:
                    new_dp[(new_balance, new_min)] = flips
        else:
            # Option 1: flip to '1'
            new_balance_flip = current_balance + 1
            new_min_flip = min(min_balance, new_balance_flip)
            if new_balance_flip >= min_balance:
                if new_dp[(new_balance_flip, new_min_flip)] > flips + 1:
                    new_dp[(new_balance_flip, new_min_flip)] = flips + 1
            # Option 2: not flip
            new_balance_noflip = current_balance - 1
            if new_balance_noflip >= min_balance:
                new_min_noflip = min(min_balance, new_balance_noflip)
                if new_dp[(new_balance_noflip, new_min_noflip)] > flips:
                    new_dp[(new_balance_noflip, new_min_noflip)] = flips
    dp = new_dp

if not dp:
    print(-1)  # Not possible, but according to problem constraints, input is always valid.
else:
    print(min(dp.values()))
0