結果

問題 No.3230 Mutual Corresponding System
コンテスト
ユーザー ゼット
提出日時 2025-08-11 23:18:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,723 ms / 2,000 ms
コード長 925 bytes
コンパイル時間 267 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 88,168 KB
最終ジャッジ日時 2025-08-11 23:18:31
合計ジャッジ時間 27,362 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N,M=map(int,input().split())
T=list(map(int,input().split()))
result=T[:]
A=[list(map(int,input().split())) for i in range(N)]
v=[[[0]*N for i in range(N)] for k in range(60)]
for i in range(N):
  for j in range(N):
    v[0][i][j]=A[i][j]
for k in range(1,60):
  for i in range(N):
    for j in range(N):
      ans=0
      for w in range(N):
        ans=max(ans,v[k-1][i][w]+v[k-1][w][j])
      v[k][i][j]=ans
result=[0]*N
B=-1
for k in range(60):
  if (M>>k)&1:
    if B==-1:
      B=[[0]*N for i in range(N)]
      for i in range(N):
        B[i]=v[k][i][:]
    else:
      B2=[[0]*N for i in range(N)]
      for i in range(N):
        for j in range(N):
          ans=0
          for w in range(N):
            ans=max(ans,B[i][w]+v[k][w][j])
          B2[i][j]=ans
      for i in range(N):
        B[i]=B2[i][:]
result=[0]*N
for i in range(N):
  for j in range(N):
    result[j]=max(result[j],T[i]+B[i][j])
print(*result)
0