結果

問題 No.484 収穫
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:48:37
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,489 bytes
コンパイル時間 418 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 540,760 KB
最終ジャッジ日時 2025-03-20 18:50:24
合計ジャッジ時間 24,702 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 9 MLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

dp = [[[INF] * 2 for _ in range(n)] for __ in range(n)]

# Initialize for single-cell intervals
for i in range(n):
    dp[i][i][0] = A[i]
    dp[i][i][1] = A[i]

# Process intervals of increasing length
for length in range(1, n):
    for l in range(n - length):
        r = l + length
        # Check if we can extend to the left (to l)
        # From the right end of [l+1][r]
        candidate_left_from_right = dp[l+1][r][1] + (r - l)
        new_time = max(candidate_left_from_right, A[l])
        if new_time < dp[l][r][0]:
            dp[l][r][0] = new_time
        # From the left end of [l+1][r]
        candidate_left_from_left = dp[l+1][r][0] + 1
        new_time = max(candidate_left_from_left, A[l])
        if new_time < dp[l][r][0]:
            dp[l][r][0] = new_time

        # Check if we can extend to the right (to r)
        # From the left end of [l][r-1]
        candidate_right_from_left = dp[l][r-1][0] + (r - l)
        new_time = max(candidate_right_from_left, A[r])
        if new_time < dp[l][r][1]:
            dp[l][r][1] = new_time
        # From the right end of [l][r-1]
        candidate_right_from_right = dp[l][r-1][1] + 1
        new_time = max(candidate_right_from_right, A[r])
        if new_time < dp[l][r][1]:
            dp[l][r][1] = new_time

# The answer is the minimum of the two possible end states for the full interval [0, n-1]
print(min(dp[0][n-1][0], dp[0][n-1][1]))
0