結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    if N < 3:
        print(0)
        return
    
    is_peak = [False] * N
    queue = deque()
    
    for j in range(1, N-1):
        if A[j-1] < A[j] and A[j] > A[j+1]:
            is_peak[j] = True
            queue.append(j)
    
    count = 0
    
    while queue:
        j = queue.popleft()
        if not is_peak[j]:
            continue
        
        left_val = A[j-1]
        right_val = A[j+1]
        new_val = min(left_val, right_val) - 1
        A[j] = new_val
        count += 1
        is_peak[j] = False
        
        for neighbor in [j-1, j+1]:
            if neighbor < 1 or neighbor >= N-1:
                continue
            if A[neighbor-1] < A[neighbor] and A[neighbor] > A[neighbor+1]:
                if not is_peak[neighbor]:
                    is_peak[neighbor] = True
                    queue.append(neighbor)
            else:
                if is_peak[neighbor]:
                    is_peak[neighbor] = False
    
    print(count)

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