結果
問題 |
No.3230 Mutual Corresponding System
|
ユーザー |
|
提出日時 | 2025-08-08 22:30:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,622 ms / 2,000 ms |
コード長 | 1,131 bytes |
コンパイル時間 | 301 ms |
コンパイル使用メモリ | 81,720 KB |
実行使用メモリ | 77,300 KB |
最終ジャッジ日時 | 2025-08-08 22:30:45 |
合計ジャッジ時間 | 12,612 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
import sys input = lambda :sys.stdin.readline()[:-1] ni = lambda :int(input()) na = lambda :list(map(int,input().split())) yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES") no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO") ####################################################################### inf = 10 ** 18 def mat_mul(A, B): C = [[-inf for j in range(len(B[0]))] for i in range(len(A))] for i in range(len(A)): for j in range(len(B[0])): for k in range(len(B)): C[i][j] = max(C[i][j], A[i][k] + B[k][j]) # print(A, B, C) return C def mat_pow(A, x): assert len(A)==len(A[0]) n = len(A) R = [[-inf for j in range(n)]for i in range(n)] for i in range(n): R[i][i] = 0 while x > 0: if x&1: R = mat_mul(R, A) A = mat_mul(A,A) x >>= 1 return R n, m = na() t = [na()] T = t a = [na() for i in range(n)] # for i in range(n): # a[i][i] = -inf # for i in range(m): # T = mat_mul(T, a) # print(T) res = mat_mul(t, mat_pow(a, m)) print(*res[0])