結果

問題 No.2036 Max Middle
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:31:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,157 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 82,008 KB
実行使用メモリ 283,544 KB
最終ジャッジ日時 2025-04-16 15:35:47
合計ジャッジ時間 4,376 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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