結果

問題 No.2036 Max Middle
ユーザー lam6er
提出日時 2025-04-15 21:09:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,157 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,120 KB
実行使用メモリ 55,632 KB
最終ジャッジ日時 2025-04-15 21:15:58
合計ジャッジ時間 4,494 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    if n < 3:
        print(0)
        return
    
    queue = deque()
    in_queue = [False] * n
    
    # Initialize queue with initial peaks
    for j in range(1, n-1):
        if arr[j-1] < arr[j] and arr[j] > arr[j+1]:
            queue.append(j)
            in_queue[j] = True
    
    count = 0
    
    while queue:
        j = queue.popleft()
        in_queue[j] = False
        
        # Check if current j is still a peak
        if j < 1 or j >= n-1:
            continue
        if not (arr[j-1] < arr[j] and arr[j] > arr[j+1]):
            continue
        
        # Perform the operation
        count += 1
        new_val = min(arr[j-1], arr[j+1]) - 1
        arr[j] = new_val
        
        # Check neighboring positions and add them to the queue if necessary
        for k in [j-1, j, j+1]:
            if 1 <= k < n-1:
                if not in_queue[k]:
                    queue.append(k)
                    in_queue[k] = True
    
    print(count)

if __name__ == "__main__":
    main()
0