#1059718 (PyPy3) No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX