結果

問題 No.484 収穫
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:05:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,150 bytes
コンパイル時間 383 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 426,760 KB
最終ジャッジ日時 2025-06-12 15:06:46
合計ジャッジ時間 22,365 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 12 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    INF = 1 << 60
    dp = [[[INF] * 2 for _ in range(N + 2)] for __ in range(N + 2)]
    
    for i in range(1, N + 1):
        dp[i][i][0] = max(A[i - 1], 0)
        dp[i][i][1] = max(A[i - 1], 0)
    
    for k in range(1, N):
        for l in range(1, N - k + 1 + 1):
            r = l + k - 1
            if r > N:
                continue
            
            # Current position is left end (l)
            current = dp[l][r][0]
            if current < INF:
                # Move left
                if l > 1:
                    new_l = l - 1
                    new_r = r
                    time = current + 1
                    required = max(time, A[new_l - 1])
                    if required < dp[new_l][new_r][0]:
                        dp[new_l][new_r][0] = required
                # Move right
                if r < N:
                    new_l = l
                    new_r = r + 1
                    time = current + (r - l) + 1
                    required = max(time, A[new_r - 1])
                    if required < dp[new_l][new_r][1]:
                        dp[new_l][new_r][1] = required
            
            # Current position is right end (r)
            current = dp[l][r][1]
            if current < INF:
                # Move right
                if r < N:
                    new_l = l
                    new_r = r + 1
                    time = current + 1
                    required = max(time, A[new_r - 1])
                    if required < dp[new_l][new_r][1]:
                        dp[new_l][new_r][1] = required
                # Move left
                if l > 1:
                    new_l = l - 1
                    new_r = r
                    time = current + (r - l) + 1
                    required = max(time, A[new_l - 1])
                    if required < dp[new_l][new_r][0]:
                        dp[new_l][new_r][0] = required
    
    ans = min(dp[1][N][0], dp[1][N][1])
    print(ans)

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