結果

問題 No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
ユーザー tamatotamato
提出日時 2021-12-09 00:51:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 411 ms / 2,000 ms
コード長 1,596 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 80,640 KB
最終ジャッジ日時 2024-07-16 11:47:43
合計ジャッジ時間 14,172 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

mod = 1000000007
eps = 10**-9
inf = 10 ** 30
def main():
import sys
input = sys.stdin.readline
C = list(map(int, input().split()))
K = list(map(int, input().split()))
N = int(input())
D_list = [[[-inf] * 17 for _ in range(17)] for _ in range(26)]
for i in range(26):
for v in range(17):
D_list[i][v][v] = 0
for _ in range(N):
S, A, B, E = input().split()
A = int(A)
B = int(B)
E = int(E)
for s in S:
i = ord(s) - 65
D_list[i][A][B] = max(D_list[i][A][B], E)
D_list[i][B][A] = max(D_list[i][B][A], E)
cost = [0] * 17
cost[0] = -inf
for i in range(26):
D = D_list[i]
DD = [None] * 25
DD[0] = D
for lv in range(1, 25):
DD[lv] = [[-inf] * 17 for _ in range(17)]
for u in range(1, 17):
for v in range(1, 17):
for w in range(1, 17):
DD[lv][u][v] = max(DD[lv][u][v], DD[lv - 1][u][w] + DD[lv - 1][w][v])
dist = [-inf] * 17
dist[C[i]] = 0
for lv in range(25):
if K[i] >> lv & 1:
dist_new = [-inf] * 17
for u in range(17):
for v in range(17):
dist_new[v] = max(dist_new[v], dist[u] + DD[lv][u][v])
dist = dist_new
for j in range(1, 17):
cost[j] += dist[j]
ans = max(cost)
if ans < -10 ** 20:
print("Impossible")
else:
print(ans)
if __name__ == '__main__':
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0