結果

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

ソースコード

diff # 

n, k = map(int, input().split())
a = list(map(int, input().split()))
c = list(map(int, input().split()))

# 拆环成链
a = a + a
c = c + c

total_sum = sum(a[:n])

# 预处理前缀和
prefix = [0] * (2 * n + 1)
for i in range(2 * n):
    prefix[i + 1] = prefix[i] + a[i]

def get_sum(i, j):
    return prefix[j + 1] - prefix[i]

# 初始化DP表，dp[i][j]是一个集合，存储可以合并成的颜色
dp = [[set() for _ in range(2 * n)] for _ in range(2 * n)]

for i in range(2 * n):
    dp[i][i].add(c[i])

# 动态规划处理所有可能的区间
for length in range(2, n + 1):
    for i in range(2 * n - length + 1):
        j = i + length - 1
        for split in range(i, j):
            left = dp[i][split]
            right = dp[split + 1][j]
            if not left or not right:
                continue
            for c1 in left:
                for c2 in right:
                    if abs(c1 - c2) <= k:
                        dp[i][j].add(c1)
                        dp[i][j].add(c2)

# 检查整个环是否可以合并
can_merge = False
for i in range(n):
    j = i + n - 1
    if j >= 2 * n:
        break
    if len(dp[i][j]) > 0:
        can_merge = True
        break

if can_merge:
    print(total_sum)
    exit()

# 寻找最大的子区间
max_sum = 0
for i in range(2 * n):
    for j in range(i, 2 * n):
        if j - i + 1 > n:
            continue
        if len(dp[i][j]) > 0:
            current_sum = get_sum(i, j)
            if current_sum > max_sum:
                max_sum = current_sum

print(max_sum)
0