結果

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

ソースコード

diff # 

from heapq import heappush, heappop

def solve(N, S):
    # Convert string to array: '0' -> +1, '1' -> -1
    A = [1 if c == '0' else -1 for c in S]
    
    # Priority queue to store indices of '0's (max heap using negative indices)
    pq = []
    
    # Running prefix sum
    prefix_sum = 0
    
    # List to store prefix sums up to current position
    prefix_sums = [0]  # Initial prefix sum before first character
    
    # Count of operations
    operations = 0
    
    # Process each character
    for i in range(N):
        # Update prefix sum with current character's value
        prefix_sum += A[i]
        
        # If current character is '0', add its index to priority queue
        if A[i] == 1:
            heappush(pq, -i)  # Negative index for max heap behavior
        
        # Check if current prefix sum violates the "good" condition
        min_prev = min(prefix_sums)
        while prefix_sum > min_prev and pq:
            # Get the rightmost '0' index
            idx = -heappop(pq)
            # Flip '0' to '1': +1 becomes -1, reducing prefix sum by 2
            A[idx] = -1
            prefix_sum -= 2
            operations += 1
        
        # Store the current prefix sum
        prefix_sums.append(prefix_sum)
        # Optional: Keep prefix_sums manageable by removing oldest if unnecessary
        if len(prefix_sums) > i - 1:
            prefix_sums.pop(0)
    
    return operations

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

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