結果
問題 | No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
mod = 1000000007eps = 10**-9inf = 10 ** 30def main():import sysinput = sys.stdin.readlineC = 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] = 0for _ 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) - 65D_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] * 17cost[0] = -inffor i in range(26):D = D_list[i]DD = [None] * 25DD[0] = Dfor 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] * 17dist[C[i]] = 0for lv in range(25):if K[i] >> lv & 1:dist_new = [-inf] * 17for u in range(17):for v in range(17):dist_new[v] = max(dist_new[v], dist[u] + DD[lv][u][v])dist = dist_newfor 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()