結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    INF = float('inf')
    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+1):
        for l in range(1, N - length + 2):
            r = l + length - 1
            # Check left end
            current = dp[l][r][0]
            if current != INF:
                # Move left to l-1
                if l > 1:
                    new_l = l - 1
                    new_r = r
                    time_needed = current + 1
                    new_time = max(time_needed, A[new_l - 1])
                    if new_time < dp[new_l][new_r][0]:
                        dp[new_l][new_r][0] = new_time
                # Move right to r+1
                if r < N:
                    new_l = l
                    new_r = r + 1
                    move_time = (new_r - l)
                    time_needed = current + move_time
                    new_time = max(time_needed, A[new_r - 1])
                    if new_time < dp[new_l][new_r][1]:
                        dp[new_l][new_r][1] = new_time
            # Check right end
            current = dp[l][r][1]
            if current != INF:
                # Move right to r+1
                if r < N:
                    new_l = l
                    new_r = r + 1
                    time_needed = current + 1
                    new_time = max(time_needed, A[new_r - 1])
                    if new_time < dp[new_l][new_r][1]:
                        dp[new_l][new_r][1] = new_time
                # Move left to l-1
                if l > 1:
                    new_l = l - 1
                    new_r = r
                    move_time = (r - new_l)
                    time_needed = current + move_time
                    new_time = max(time_needed, A[new_l - 1])
                    if new_time < dp[new_l][new_r][0]:
                        dp[new_l][new_r][0] = new_time
    
    result = min(dp[1][N][0], dp[1][N][1])
    print(result)

if __name__ == "__main__":
    main()
0