結果

問題 No.484 収穫
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:23:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,628 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 541,204 KB
最終ジャッジ日時 2025-04-16 16:24:35
合計ジャッジ時間 23,748 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 9 MLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

# Initialize DP table
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(1, n):
    for l in range(1, n - length + 1):
        r = l + length
        # Case 1: Extend to the left from the left end of [l+1, r]
        if l + 1 <= r:
            current = dp[l+1][r][0]
            time = current + 1
            harvest = max(time, a[l-1])
            if harvest < dp[l][r][0]:
                dp[l][r][0] = harvest
        # Case 2: Extend to the left from the right end of [l+1, r]
        if l + 1 <= r:
            current = dp[l+1][r][1]
            steps = (r - (l+1)) + 1  # Steps from right end of [l+1, r] to l
            time = current + steps
            harvest = max(time, a[l-1])
            if harvest < dp[l][r][0]:
                dp[l][r][0] = harvest
        # Case 3: Extend to the right from the left end of [l, r-1]
        if r - 1 >= l:
            current = dp[l][r-1][0]
            steps = (r-1 - l) + 1  # Steps from left end of [l, r-1] to r
            time = current + steps
            harvest = max(time, a[r-1])
            if harvest < dp[l][r][1]:
                dp[l][r][1] = harvest
        # Case 4: Extend to the right from the right end of [l, r-1]
        if r - 1 >= l:
            current = dp[l][r-1][1]
            time = current + 1
            harvest = max(time, a[r-1])
            if harvest < dp[l][r][1]:
                dp[l][r][1] = harvest

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