結果

問題 No.484 収穫
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:03:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,879 bytes
コンパイル時間 144 ms
コンパイル使用メモリ 82,200 KB
実行使用メモリ 203,324 KB
最終ジャッジ日時 2025-06-12 20:08:45
合計ジャッジ時間 5,854 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 12 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    INF = float('inf')
    left = [[INF] * (N + 2) for _ in range(N + 2)]
    right = [[INF] * (N + 2) for _ in range(N + 2)]
    
    for i in range(1, N + 1):
        left[i][i] = A[i - 1]
        right[i][i] = A[i - 1]
    
    for length in range(1, N):
        for l in range(1, N - length + 1):
            r = l + length
            
            # Expand from left end of [l, r-1] to right
            current_left = left[l][r - 1]
            if current_left != INF:
                time = current_left + (r - l)
                required = max(time, A[r - 1])
                if required < right[l][r]:
                    right[l][r] = required
            
            # Expand from right end of [l, r-1] to right
            current_right = right[l][r - 1]
            if current_right != INF:
                time = current_right + 1
                required = max(time, A[r - 1])
                if required < right[l][r]:
                    right[l][r] = required
            
            # Expand from right end of [l+1, r] to left
            current_right_sub = right[l + 1][r]
            if current_right_sub != INF:
                time = current_right_sub + (r - l)
                required = max(time, A[l - 1])
                if required < left[l][r]:
                    left[l][r] = required
            
            # Expand from left end of [l+1, r] to left
            current_left_sub = left[l + 1][r]
            if current_left_sub != INF:
                time = current_left_sub + 1
                required = max(time, A[l - 1])
                if required < left[l][r]:
                    left[l][r] = required
    
    print(min(left[1][N], right[1][N]))

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