結果

問題 No.2036 Max Middle
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:38:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,178 bytes
コンパイル時間 264 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 276,356 KB
最終ジャッジ日時 2025-06-12 13:44:06
合計ジャッジ時間 4,599 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    peak = [False] * (n - 2)  # 0-based indices for peaks
    for i in range(n - 2):
        if A[i] < A[i+1] and A[i+1] > A[i+2]:
            peak[i] = True
    
    q = deque()
    for i in range(n - 2):
        if peak[i]:
            q.append(i)
    
    count = 0
    
    while q:
        i = q.popleft()
        if not peak[i]:
            continue
        
        # Perform the operation
        min_val = min(A[i], A[i+2])
        A[i+1] = min_val - 1
        count += 1
        
        # Mark current peak as non-peak
        peak[i] = False
        
        # Check neighboring positions for new peaks
        for dj in [-1, 0, 1]:
            j = i + dj
            if 0 <= j < n - 2:
                current_peak = (A[j] < A[j+1] and A[j+1] > A[j+2])
                if current_peak != peak[j]:
                    peak[j] = current_peak
                    if current_peak:
                        q.append(j)
    
    print(count)

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