結果
問題 |
No.572 妖精の演奏
|
ユーザー |
![]() |
提出日時 | 2019-09-17 12:24:42 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 2,106 bytes |
コンパイル時間 | 2,163 ms |
コンパイル使用メモリ | 112,772 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-07 10:28:27 |
合計ジャッジ時間 | 3,121 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include<iostream> #include<string> #include<cstdio> #include<vector> #include<cmath> #include<algorithm> #include<functional> #include<iomanip> #include<queue> #include<ciso646> #include<random> #include<map> #include<set> #include<complex> #include<bitset> #include<stack> #include<unordered_map> #include<utility> #include<tuple> using namespace std; typedef long long ll; typedef unsigned int ui; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair<int, int> P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define Rep(i,sta,n) for(int i=sta;i<n;i++) #define Per(i,sta,n) for(int i=n-1;i>=sta;i--) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; typedef complex<ld> Point; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair<ll, ll> LP; typedef vector< vector< ll > > mat; typedef vector< ll > vec; mat mtmul(mat &A, mat &B){ mat C(A.size(), vec(B[0].size())); rep(i, (int)A.size()) { rep(k, (int)B.size()) { rep(j, (int)B[0].size()) { C[i][j] = max(C[i][j] , (A[i][k] + B[k][j]) ) ; } } } return C; } mat mtpow(mat A, ll n) { mat B(A.size(), vec(A.size())); rep(i, (int)A.size()) { rep(j,(int)A.size()){ B[i][j]=A[i][j]; } } n--; while (n > 0) { if (n&(ll)1)B = mtmul(B, A); A = mtmul(A, A); n >>= 1; } return B; } int n,m; mat A; void solve(){ cin >> n >> m; A.resize(m,vec(m)); rep(i,m){ rep(j,m){ cin >> A[i][j]; } } mat B=mtpow(A,n-1); ll ans=0; rep(i,m){ rep(j,m){ ans=max(B[i][j],ans); } } cout << ans << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }