結果

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

ソースコード

diff # 

from heapq import heappush, heappop

def solve(N, S):
    # Convert string to array of +1 ('0') and -1 ('1')
    A = [1 if c == '0' else -1 for c in S]
    # Priority queue to store indices of '0's (use negative index for max heap)
    pq = []
    # Prefix sum
    prefix_sum = 0
    # Multiset of prefix sums (simulated with a list for simplicity)
    prefix_sums = [0]  # P[0] = 0
    operations = 0
    
    for i in range(N):
        # Add current character's contribution to prefix sum
        prefix_sum += A[i]
        # If current character is '0', add its index to priority queue
        if A[i] == 1:
            heappush(pq, -i)  # Negative for max heap (later indices first)
        
        # Check if current prefix sum violates the condition
        min_prev = min(prefix_sums)
        while prefix_sum > min_prev:
            # Need to reduce prefix_sum by changing a '0' to '1'
            if not pq:
                return -1  # Impossible case (should not occur given constraints)
            # Get the rightmost '0' index
            idx = -heappop(pq)
            # Change '0' to '1' at idx
            A[idx] = -1
            # Update prefix sum: changing '0' (+1) to '1' (-1) reduces sum by 2
            prefix_sum -= 2
            operations += 1
        
        # Add current prefix sum to the list
        prefix_sums.append(prefix_sum)
        # Remove oldest prefix sum if we have more than needed (optional optimization)
        if len(prefix_sums) > i - 1:
            prefix_sums.pop(0)
    
    return operations

# Input
N = int(input())
S = input().strip()

# Output
print(solve(N, S))
0