結果

問題 No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:14:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,782 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 408,728 KB
最終ジャッジ日時 2025-06-12 19:14:31
合計ジャッジ時間 20,112 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0

    # Read initial colors for A-Z
    C = list(map(int, input[ptr:ptr+26]))
    ptr += 26

    # Read K values for A-Z
    K = list(map(int, input[ptr:ptr+26]))
    ptr += 26

    N = int(input[ptr])
    ptr += 1

    # For each ability, store which trees can use it
    abilities = []
    for _ in range(N):
        S = input[ptr]
        A = int(input[ptr+1])
        B = int(input[ptr+2])
        E = int(input[ptr+3])
        ptr +=4
        abilities.append( (S, A, B, E) )

    # For each tree (A-Z), collect their 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, precompute max_e matrix and DP
    m_max = 32  # Adjust this based on time constraints
    all_tree_info = []
    for tree_idx in range(26):
        initial_color = C[tree_idx]
        K_alpha = K[tree_idx]

        # Initialize max_e matrix
        max_e = [ [-10**18 for _ in range(17)] for _ in range(17) ]
        for A, B, E in tree_abilities[tree_idx]:
            if E > max_e[A][B]:
                max_e[A][B] = E
            if E > max_e[B][A]:
                max_e[B][A] = E

        # Compute DP
        dp = [ [-10**18 for _ in range(17)] for _ in range(m_max+1) ]
        dp[0][initial_color] = 0
        for m in range(1, m_max+1):
            for c_prev in range(1, 17):
                if dp[m-1][c_prev] == -10**18:
                    continue
                for c_new in range(1, 17):
                    e = max_e[c_prev][c_new]
                    if e == -10**18:
                        continue
                    new_energy = dp[m-1][c_prev] + e
                    if new_energy > dp[m][c_new]:
                        dp[m][c_new] = new_energy

        # Precompute max_e_single and partner for each color
        max_e_single = [ -10**18 for _ in range(17) ]
        partner = [ -1 for _ in range(17) ]
        for d in range(1, 17):
            max_val = -10**18
            partner_d = -1
            for c_new in range(1, 17):
                if max_e[d][c_new] > max_val:
                    max_val = max_e[d][c_new]
                    partner_d = c_new
            max_e_single[d] = max_val
            partner[d] = partner_d

        all_tree_info.append( (dp, max_e_single, partner, K_alpha) )

    # For each possible target color c (1-16), check if all trees can reach it
    max_total = -10**18
    for target_color in range(1, 17):
        total = 0
        possible = True
        for tree_idx in range(26):
            dp, max_e_single, partner, K_alpha = all_tree_info[tree_idx]
            max_energy = -10**18

            # Check m up to min(K_alpha, m_max)
            max_m = min(K_alpha, m_max)
            for m in range(0, max_m+1):
                if dp[m][target_color] > max_energy:
                    max_energy = dp[m][target_color]

            # Check cycles
            for d in range(1, 17):
                if max_e_single[d] <= 0:
                    continue
                partner_d = partner[d]
                if partner_d == -1:
                    continue
                for m in range(0, max_m+1):
                    if m > K_alpha:
                        continue
                    current_energy = dp[m][d]
                    if current_energy == -10**18:
                        continue
                    s = K_alpha - m
                    if s < 0:
                        continue

                    if target_color == d:
                        # Need even steps
                        s_even = s if s % 2 == 0 else s -1
                        if s_even <0:
                            continue
                        total_energy = current_energy + s_even * max_e_single[d]
                        if total_energy > max_energy:
                            max_energy = total_energy
                    elif target_color == partner_d:
                        # Need odd steps
                        s_odd = s if s %2 ==1 else s-1
                        if s_odd <1:
                            continue
                        total_energy = current_energy + s_odd * max_e_single[d]
                        if total_energy > max_energy:
                            max_energy = total_energy

            if max_energy == -10**18:
                possible = False
                break
            total += max_energy

        if possible and total > max_total:
            max_total = total

    if max_total == -10**18:
        print("Impossible")
    else:
        print(max_total)

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