結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 227 ms
77,568 KB
testcase_01 AC 226 ms
77,184 KB
testcase_02 AC 300 ms
77,824 KB
testcase_03 AC 281 ms
78,464 KB
testcase_04 AC 338 ms
77,632 KB
testcase_05 AC 300 ms
78,656 KB
testcase_06 AC 323 ms
77,860 KB
testcase_07 AC 263 ms
78,272 KB
testcase_08 AC 310 ms
78,120 KB
testcase_09 AC 325 ms
78,268 KB
testcase_10 AC 274 ms
78,416 KB
testcase_11 AC 299 ms
78,164 KB
testcase_12 AC 310 ms
80,640 KB
testcase_13 AC 242 ms
77,568 KB
testcase_14 AC 218 ms
77,824 KB
testcase_15 AC 356 ms
78,208 KB
testcase_16 AC 347 ms
77,568 KB
testcase_17 AC 240 ms
77,312 KB
testcase_18 AC 268 ms
78,080 KB
testcase_19 AC 213 ms
77,952 KB
testcase_20 AC 271 ms
77,568 KB
testcase_21 AC 391 ms
77,952 KB
testcase_22 AC 411 ms
78,080 KB
testcase_23 AC 256 ms
78,080 KB
testcase_24 AC 401 ms
77,312 KB
testcase_25 AC 227 ms
77,824 KB
testcase_26 AC 224 ms
77,568 KB
testcase_27 AC 276 ms
77,824 KB
testcase_28 AC 212 ms
78,080 KB
testcase_29 AC 201 ms
77,804 KB
testcase_30 AC 353 ms
77,312 KB
testcase_31 AC 210 ms
77,820 KB
testcase_32 AC 200 ms
77,208 KB
testcase_33 AC 262 ms
77,696 KB
testcase_34 AC 228 ms
77,312 KB
testcase_35 AC 246 ms
77,440 KB
testcase_36 AC 231 ms
77,184 KB
testcase_37 AC 246 ms
77,312 KB
testcase_38 AC 280 ms
78,384 KB
testcase_39 AC 329 ms
77,428 KB
testcase_40 AC 269 ms
77,100 KB
testcase_41 AC 269 ms
77,492 KB
権限があれば一括ダウンロードができます

ソースコード

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()
0