結果

問題 No.2423 Merge Stones
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:50:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,846 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 373 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 65,636 KB
最終ジャッジ日時 2025-03-20 20:50:32
合計ジャッジ時間 7,227 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 61
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))
    
    max_C = max(C)
    
    # Extend the array to handle circularity
    A_ext = A * 2
    C_ext = C * 2
    size = 2 * N
    
    # Initialize DP table
    dp = [[dict() for _ in range(size)] for _ in range(size)]
    
    for i in range(size):
        c = C_ext[i]
        dp[i][i][c] = A_ext[i]
    
    for L in range(2, N + 1):
        for i in range(size - L + 1):
            j = i + L - 1
            current_dp = {}
            for k in range(i, j):
                left = dp[i][k]
                right = dp[k+1][j]
                for c1 in left:
                    for c2 in right:
                        if abs(c1 - c2) > K:
                            continue
                        total = left[c1] + right[c2]
                        # Choose c1
                        if c1 in current_dp:
                            if total > current_dp[c1]:
                                current_dp[c1] = total
                        else:
                            current_dp[c1] = total
                        # Choose c2
                        if c2 in current_dp:
                            if total > current_dp[c2]:
                                current_dp[c2] = total
                        else:
                            current_dp[c2] = total
            dp[i][j] = current_dp
    
    max_val = 0
    for i in range(size):
        for j in range(i, min(i + N, size)):
            current_dict = dp[i][j]
            for key in current_dict:
                if current_dict[key] > max_val:
                    max_val = current_dict[key]
    print(max_val)

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