結果

問題 No.484 収穫
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:34:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,018 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 425,936 KB
最終ジャッジ日時 2025-03-31 17:36:13
合計ジャッジ時間 20,236 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 12 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
A = list(map(int, input().split()))
# Convert to 1-based index
A = [0] + A

INF = 10**18
# dp[l][r][0] represents time when at left end l after covering [l..r]
# dp[l][r][1] represents time when at right end r after covering [l..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]
    dp[i][i][1] = A[i]

for length in range(2, n + 1):
    for l in range(1, n - length + 2):
        r = l + length - 1
        
        # Update dp[l][r][0]: come from [l+1][r] which is left end (l+1)
        time_candidate = dp[l+1][r][0] + 1
        new_time = max(time_candidate, A[l])
        if new_time < dp[l][r][0]:
            dp[l][r][0] = new_time
        
        # Update dp[l][r][1]: come from [l][r-1] which is right end (r-1)
        time_candidate = dp[l][r-1][1] + 1
        new_time = max(time_candidate, A[r])
        if new_time < dp[l][r][1]:
            dp[l][r][1] = new_time

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