結果

問題 No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:36:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,612 bytes
コンパイル時間 145 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 132,940 KB
最終ジャッジ日時 2025-06-12 15:36:33
合計ジャッジ時間 5,183 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    from collections import defaultdict

    # 读取输入
    input = sys.stdin.read().split()
    ptr = 0

    # 读取C_alpha
    C = list(map(int, input[ptr:ptr+26]))
    ptr += 26

    # 读取K_alpha
    K = list(map(int, input[ptr:ptr+26]))
    ptr += 26

    # 读取N
    N = int(input[ptr])
    ptr += 1

    # 读取技能列表
    skills = []
    for _ in range(N):
        S = input[ptr]
        A = int(input[ptr+1])
        B = int(input[ptr+2])
        E = int(input[ptr+3])
        ptr += 4
        skills.append((S, A, B, E))

    # 预处理每个alpha的可用技能
    alpha_skills = defaultdict(list)
    for skill in skills:
        S, A, B, E = skill
        for c in S:
            alpha_skills[c].append((A, B, E))

    # 定义颜色转移的结构
    class ColorGraph:
        def __init__(self, initial_color, max_steps, skills):
            self.initial = initial_color
            self.max_steps = max_steps
            self.skills = skills
            self.size = 16
            self.adj = [[] for _ in range(self.size + 1)]  # 1-based
            for A, B, E in self.skills:
                self.adj[A].append((B, E))
                self.adj[B].append((A, E))

        def compute_max_energy(self):
            INF = -1e18
            dp = [INF] * (self.size + 1)
            dp[self.initial] = 0

            for _ in range(self.max_steps):
                new_dp = dp.copy()
                for c in range(1, self.size + 1):
                    if dp[c] == INF:
                        continue
                    for (next_c, e) in self.adj[c]:
                        if new_dp[next_c] < dp[c] + e:
                            new_dp[next_c] = dp[c] + e
                dp = new_dp

            return dp

    # 预处理每个alpha
    alpha_data = []
    for i in range(26):
        c = chr(ord('A') + i)
        initial = C[i]
        k = K[i]
        available_skills = alpha_skills.get(c, [])
        graph = ColorGraph(initial, k, available_skills)
        dp = graph.compute_max_energy()
        alpha_data.append(dp)

    # 检查每个目标颜色c是否可达
    possible = []
    for target in range(1, 17):
        total = 0
        possible_flag = True
        for i in range(26):
            dp = alpha_data[i]
            if dp[target] == -1e18:
                possible_flag = False
                break
            total += dp[target]
        if possible_flag:
            possible.append(total)

    if not possible:
        print("Impossible")
    else:
        print(max(possible))

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