結果

問題 No.2423 Merge Stones
ユーザー lam6er
提出日時 2025-03-20 20:57:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,314 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,948 KB
実行使用メモリ 76,628 KB
最終ジャッジ日時 2025-03-20 20:57:56
合計ジャッジ時間 7,310 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

    # Extend the array to handle circular case
    A_extended = A + A
    C_extended = C + C

    max_val = 0
    # Try all possible starting points
    for start in range(N):
        end = start + N
        current_A = A_extended[start:end]
        current_C = C_extended[start:end]
        # Initialize DP
        DP = [[dict() for _ in range(N)] for __ in range(N)]
        for i in range(N):
            c = current_C[i]
            DP[i][i][c] = current_A[i]
            if current_A[i] > max_val:
                max_val = current_A[i]

        for length in range(2, N+1):
            for i in range(N - length +1):
                j = i + length -1
                for k in range(i, j):
                    left = DP[i][k]
                    right = DP[k+1][j]
                    for c1 in left:
                        sum1 = left[c1]
                        for c2 in right:
                            sum2 = right[c2]
                            if abs(c1 - c2) > K:
                                continue
                            total = sum1 + sum2
                            # Update for color c1 and c2
                            if c1 in DP[i][j]:
                                if total > DP[i][j][c1]:
                                    DP[i][j][c1] = total
                            else:
                                DP[i][j][c1] = total
                            if c2 in DP[i][j]:
                                if total > DP[i][j][c2]:
                                    DP[i][j][c2] = total
                            else:
                                DP[i][j][c2] = total
                # Update max_val after processing all splits for i..j
                for c in DP[i][j]:
                    if DP[i][j][c] > max_val:
                        max_val = DP[i][j][c]

        # Check DP[0][N-1] for max_val
        final_dict = DP[0][N-1]
        for c in final_dict:
            if final_dict[c] > max_val:
                max_val = final_dict[c]

    print(max_val)

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