結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    C = list(map(int, sys.stdin.readline().split()))
    K = list(map(int, sys.stdin.readline().split()))
    N = int(sys.stdin.readline())

    abilities = [[] for _ in range(26)]
    for _ in range(N):
        parts = sys.stdin.readline().split()
        S = parts[0]
        A = int(parts[1])
        B = int(parts[2])
        E = int(parts[3])
        for c in S:
            idx = ord(c) - ord('A')
            abilities[idx].append((A, B, E))

    color_graph = [{} for _ in range(26)]
    for alpha in range(26):
        for a, b, e in abilities[alpha]:
            if a not in color_graph[alpha]:
                color_graph[alpha][a] = []
            color_graph[alpha][a].append((b, e))
            if b not in color_graph[alpha]:
                color_graph[alpha][b] = []
            color_graph[alpha][b].append((a, e))

    def compute_max_energy(alpha, start, target, max_steps):
        if max_steps < 0:
            return None
        color_dict = color_graph[alpha]
        if start not in color_dict and start != target:
            return None
        visited = {}
        queue = deque()
        queue.append((start, 0))
        visited[(start, 0)] = 0
        max_found = -float('inf')

        while queue:
            current_color, steps = queue.popleft()
            current_energy = visited[(current_color, steps)]
            if current_color == target:
                if current_energy > max_found:
                    max_found = current_energy
            if steps >= max_steps:
                continue
            for next_color, e in color_dict.get(current_color, []):
                new_steps = steps + 1
                if new_steps > max_steps:
                    continue
                new_energy = current_energy + e
                if (next_color, new_steps) not in visited or new_energy > visited.get((next_color, new_steps), -float('inf')):
                    visited[(next_color, new_steps)] = new_energy
                    queue.append((next_color, new_steps))
        if max_found == -float('inf'):
            if start == target and max_steps >= 0:
                return 0
            return None
        return max_found

    max_total = -float('inf')
    possible = False

    for target in range(1, 17):
        total = 0
        possible_flag = True
        for alpha in range(26):
            start = C[alpha]
            k = K[alpha]
            if start == target and k == 0:
                energy = 0
            else:
                energy = compute_max_energy(alpha, start, target, k)
            if energy is None:
                possible_flag = False
                break
            total += energy
        if possible_flag:
            if total > max_total:
                max_total = total
            possible = True

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

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