結果

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