結果

問題 No.3114 0→1
コンテスト
ユーザー Aldric Liew
提出日時 2025-04-20 13:44:45
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 1,621 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 305 ms
コンパイル使用メモリ 21,284 KB
実行使用メモリ 22,136 KB
最終ジャッジ日時 2026-07-10 02:15:18
合計ジャッジ時間 7,067 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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