結果

問題 No.484 収穫
ユーザー lam6er
提出日時 2025-04-16 16:21:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,184 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 234,284 KB
最終ジャッジ日時 2025-04-16 16:23:04
合計ジャッジ時間 7,094 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 12 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
a = list(map(int, input().split()))
INF = float('inf')

# Precompute the maximum value in each interval [l..r]
max_a = [[0] * (n + 2) for _ in range(n + 2)]
for l in range(1, n + 1):
    current_max = a[l - 1]
    max_a[l][l] = current_max
    for r in range(l + 1, n + 1):
        current_max = max(current_max, a[r - 1])
        max_a[l][r] = current_max

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(2, n + 1):
    for l in range(1, n - length + 2):
        r = l + length - 1
        # Compute left[l][r]
        option1 = left[l + 1][r] + 1
        option1 = max(option1, max_a[l][r])
        option2 = right[l + 1][r] + (r - l)
        option2 = max(option2, max_a[l][r])
        left[l][r] = min(option1, option2)
        # Compute right[l][r]
        option1 = left[l][r - 1] + (r - l)
        option1 = max(option1, max_a[l][r])
        option2 = right[l][r - 1] + 1
        option2 = max(option2, max_a[l][r])
        right[l][r] = min(option1, option2)

result = min(left[1][n], right[1][n])
print(result)
0