結果
問題 |
No.572 妖精の演奏
|
ユーザー |
|
提出日時 | 2022-09-14 04:16:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 133 ms / 2,000 ms |
コード長 | 1,629 bytes |
コンパイル時間 | 758 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 77,792 KB |
最終ジャッジ日時 | 2024-12-14 12:46:52 |
合計ジャッジ時間 | 3,080 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
from collections import * from itertools import * from functools import * from heapq import * import sys,math input = sys.stdin.readline N = int(input()) M = int(input()) A = [list(map(int,input().split())) for _ in range(M)] ##fの単位元を要考慮、matrix_powのCの初期化 def f(x,y): return max(x,y) def g(x,y): return x+y def matrix_mul(A,B,f,g,mod = None): nA = len(A) mA = len(A[0]) mB = len(B[0]) tmp = [[0]*mB for _ in range(nA)] if mod is None: for i in range(nA): for j in range(mB): tmp[i][j] = reduce(f,(g(A[i][k],B[k][j]) for k in range(mA))) return tmp for i in range(nA): for j in range(mB): tmp[i][j] = reduce(f,(g(A[i][k],B[k][j])%mod for k in range(mA)))%mod return tmp def matrix_pow(A,n,f,g,mod = None): nbit = list(str(bin(n))[2:]) nbit = [int(i) for i in nbit] N = len(A) INF = (1<<60) C = [[-INF]*N for _ in range(N)] B = A for i in range(N): C[i][i] = 0 if mod is None: if f is None: for i in range(len(nbit)): if nbit[-1-i] == 1: C = matrix_mul(C,B,f,g) B = matrix_mul(B,B,f,g) return C for i in range(len(nbit)): if nbit[-1-i] == 1: C = matrix_mul(C,B,f,g,mod=mod) B = matrix_mul(B,B,f,g,mod=mod) return C I = [[0] for _ in range(M)] X = matrix_mul(matrix_pow(A,N-1,f,g),I,f,g) ans = -1 for x in X: ans = max(ans,x[0]) print(ans)