結果

問題 No.2423 Merge Stones
ユーザー gew1fw
提出日時 2025-06-12 14:46:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,784 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 274,452 KB
最終ジャッジ日時 2025-06-12 14:48:09
合計ジャッジ時間 6,444 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

    INF = float('-inf')
    MAX_COLOR = 51

    allow = [ [False]*MAX_COLOR for _ in range(MAX_COLOR) ]
    for c1 in range(MAX_COLOR):
        for c2 in range(MAX_COLOR):
            if abs(c1 - c2) <= K:
                allow[c1][c2] = True

    A_prime = A*2
    C_prime = C*2

    dp = [ [ [INF]*MAX_COLOR for _ in range(2*N) ] for __ in range(2*N) ]

    for i in range(2*N):
        c = C_prime[i]
        a = A_prime[i]
        dp[i][i][c] = a

    for l in range(2, N+1):
        for i in range(2*N):
            j = i + l -1
            if j >= 2*N:
                continue
            for k in range(i, j):
                for c1 in range(MAX_COLOR):
                    if dp[i][k][c1] == INF:
                        continue
                    for c2 in range(MAX_COLOR):
                        if dp[k+1][j][c2] == INF:
                            continue
                        if allow[c1][c2]:
                            merged = dp[i][k][c1] + dp[k+1][j][c2]
                            if merged > dp[i][j][c1]:
                                dp[i][j][c1] = merged
                            if merged > dp[i][j][c2]:
                                dp[i][j][c2] = merged

    max_magic = 0
    for i in range(N):
        for l in range(1, N+1):
            j = i + l -1
            if j >= 2*N:
                continue
            for c in range(MAX_COLOR):
                if dp[i][j][c] > max_magic:
                    max_magic = dp[i][j][c]

    print(max_magic)

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