結果

問題 No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
コンテスト
ユーザー lam6er
提出日時 2025-03-26 16:00:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,780 bytes
コンパイル時間 383 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 129,132 KB
最終ジャッジ日時 2025-03-26 16:01:20
合計ジャッジ時間 6,408 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 WA * 3 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    C = list(map(int, input[ptr:ptr+26]))
    ptr += 26
    K = list(map(int, input[ptr:ptr+26]))
    ptr += 26
    N = int(input[ptr])
    ptr += 1

    # Read all abilities
    abilities = []
    for _ in range(N):
        S = input[ptr]
        ptr +=1
        A = int(input[ptr])
        ptr +=1
        B = int(input[ptr])
        ptr +=1
        E = int(input[ptr])
        ptr +=1
        abilities.append( (S, A, B, E) )

    # Preprocess: for each tree (A-Z), collect its applicable abilities
    tree_abilities = [[] for _ in range(26)]
    for s, a, b, e in abilities:
        for c in s:
            idx = ord(c) - ord('A')
            tree_abilities[idx].append( (a, b, e) )

    # For each tree, compute DP and calculate for each color the maximum energy
    tree_data = []
    for alpha in range(26):
        initial_color = C[alpha]
        k_alpha = K[alpha]
        applicable = tree_abilities[alpha]
        # DP: steps 0..32 (inclusive), colors 1..16
        max_steps = 32
        dp = [ [-float('inf')]*17 for _ in range(max_steps + 1) ]  # steps 0..32
        dp[0][initial_color] = 0
        for m in range(max_steps):
            for c in range(1, 17):
                if dp[m][c] == -float('inf'):
                    continue
                for (A, B, E) in applicable:
                    if c == A:
                        new_c = B
                        energy = dp[m][c] + E
                    elif c == B:
                        new_c = A
                        energy = dp[m][c] + E
                    else:
                        new_c = c
                        energy = dp[m][c]
                    if energy > dp[m+1][new_c]:
                        dp[m+1][new_c] = energy
        # Precompute for each color the best possible cycle
        cycle_e = [0]*17  # cycle_e[c] is max 2*e for abilities where A or B is c and e positive
        for c in range(1,17):
            max_e = 0
            for (A, B, e) in applicable:
                if (A == c or B == c) and e > 0:
                    if e > max_e:
                        max_e = e
            cycle_e[c] = max_e * 2  # each pair of steps gives 2*e

        # For each color c, compute the maximum energy achievable
        color_energy = {}
        for c in range(1,17):
            max_energy = -float('inf')
            for m in range(0, max_steps +1):
                if m > k_alpha:
                    continue
                if dp[m][c] == -float('inf'):
                    continue
                remaining = k_alpha - m
                if remaining <0:
                    continue
                # Compute added energy from cycles
                added = 0
                if cycle_e[c] >0:
                    pairs = remaining // 2
                    added = pairs * cycle_e[c]
                total = dp[m][c] + added
                if total > max_energy:
                    max_energy = total
            if max_energy != -float('inf'):
                color_energy[c] = max_energy
            else:
                color_energy[c] = None  # means cannot reach
        tree_data.append(color_energy)

    # Check all possible colors
    max_total = -float('inf')
    for target in range(1, 17):
        total = 0
        valid = True
        for alpha in range(26):
            c_energy = tree_data[alpha].get(target, None)
            if c_energy is None:
                valid = False
                break
            total += c_energy
        if valid and total > max_total:
            max_total = total
    if max_total == -float('inf'):
        print("Impossible")
    else:
        print(max_total)

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