結果

問題 No.484 収穫
ユーザー gew1fw
提出日時 2025-06-12 20:03:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,329 bytes
コンパイル時間 229 ms
コンパイル使用メモリ 81,804 KB
実行使用メモリ 542,472 KB
最終ジャッジ日時 2025-06-12 20:09:07
合計ジャッジ時間 29,747 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 9 MLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

# dp[l][r][0] is the minimal maximum time when covering [l..r] and ending at l
# dp[l][r][1] is the same but ending at r
dp = [[[INF] * 2 for _ in range(n + 2)] for __ in range(n + 2)]

for i in range(1, n + 1):
    dp[i][i][0] = A[i - 1]
    dp[i][i][1] = A[i - 1]

for length in range(2, n + 1):
    for l in range(1, n - length + 2):
        r = l + length - 1
        # Compute dp[l][r][0]
        # Option 1: from [l+1][r][0] (left end)
        option1_time = dp[l + 1][r][0] + 1
        option1_max = max(dp[l + 1][r][0], max(option1_time, A[l - 1]))
        # Option 2: from [l+1][r][1] (right end)
        option2_time = dp[l + 1][r][1] + (r - l)
        option2_max = max(dp[l + 1][r][1], max(option2_time, A[l - 1]))
        dp[l][r][0] = min(option1_max, option2_max)
        
        # Compute dp[l][r][1]
        # Option 1: from [l][r-1][1] (right end)
        option1_time = dp[l][r - 1][1] + 1
        option1_max = max(dp[l][r - 1][1], max(option1_time, A[r - 1]))
        # Option 2: from [l][r-1][0] (left end)
        option2_time = dp[l][r - 1][0] + (r - l)
        option2_max = max(dp[l][r - 1][0], max(option2_time, A[r - 1]))
        dp[l][r][1] = min(option1_max, option2_max)

answer = min(dp[1][n][0], dp[1][n][1])
print(answer)
0