結果

問題 No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
コンテスト
ユーザー 👑 Kazun
提出日時 2021-11-25 22:37:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 941 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 122,440 KB
最終ジャッジ日時 2024-07-16 08:21:13
合計ジャッジ時間 6,808 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#Greedy 解法 (TLE)

def member_id(alpha):
    return ord(alpha)-65 # ord("A")=65

C=list(map(int,input().split()))
K=list(map(int,input().split()))

inf=float("inf"); number=16; member=26
M=[[] for _ in range(member)]
N=int(input())

for _ in range(N):
    S,A,B,E=input().split()
    A=int(A)-1; B=int(B)-1; E=int(E)
    for s in S:
        t=member_id(s)
        M[t].append((A,B,E))

Data=[[-inf]*number for _ in range(member)]
for alpha in range(member):
    DP=[-inf]*number; DP[C[alpha]-1]=0
    Data[alpha][C[alpha]-1]=0

    for _ in range(K[alpha]):
        E=DP
        DP=[-inf]*number

        for a,b,e in M[alpha]:
            DP[a]=max(DP[a],E[b]+e)
            DP[b]=max(DP[b],E[a]+e)

        for c in range(number):
            Data[alpha][c]=max(Data[alpha][c],DP[c])

F=[0]*number
for alpha in range(member):
    for c in range(number):
        F[c]+=Data[alpha][c]

Ans=max(F)
print(Ans if Ans>-inf else "Impossible")
0