結果

問題 No.2423 Merge Stones
ユーザー qwewe
提出日時 2025-05-14 12:49:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,773 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 150,904 KB
最終ジャッジ日時 2025-05-14 12:50:54
合計ジャッジ時間 6,423 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N
    C = list(map(int, input[idx:idx+N]))
    idx += N

    max_color = 50
    INF = float('-inf')

    # dp[i][l][c] = max sum for interval starting at i, length l, color c
    dp = [[[INF] * (max_color + 1) for _ in range(N + 1)] for _ in range(N)]
    color_list = [[[] for _ in range(N + 1)] for _ in range(N)]

    for i in range(N):
        c = C[i]
        dp[i][1][c] = A[i]
        color_list[i][1].append(c)

    for l in range(2, N + 1):
        for i in range(N):
            for k in range(1, l):
                left_i = i
                left_len = k
                right_i = (i + k) % N
                right_len = l - k

                left_colors = color_list[left_i][left_len]
                right_colors = color_list[right_i][right_len]

                for c1 in left_colors:
                    for c2 in right_colors:
                        if abs(c1 - c2) > K:
                            continue
                        sum_total = dp[left_i][left_len][c1] + dp[right_i][right_len][c2]

                        for new_c in [c1, c2]:
                            if sum_total > dp[i][l][new_c]:
                                if dp[i][l][new_c] == INF:
                                    color_list[i][l].append(new_c)
                                dp[i][l][new_c] = sum_total

    max_sum = max(A)
    for i in range(N):
        for l in range(1, N + 1):
            for c in color_list[i][l]:
                if dp[i][l][c] > max_sum:
                    max_sum = dp[i][l][c]

    print(max_sum)

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