結果
問題 |
No.572 妖精の演奏
|
ユーザー |
|
提出日時 | 2023-07-09 19:53:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,903 bytes |
コンパイル時間 | 2,483 ms |
コンパイル使用メモリ | 222,828 KB |
最終ジャッジ日時 | 2025-02-15 09:22:35 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef unsigned long long int ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } inline double time() { return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; int m; cin >> m; vector<vector<vector<ll>>> d(35, vector<vector<ll>>(m, vector<ll>(m))); for (int i = 0; i < m; ++i) { for (int j = 0; j < m; ++j) { cin >> d[1][i][j]; } } for (int i = 2; i < 35; ++i) { for (int j = 0; j < m; ++j) { for (int k = 0; k < m; ++k) { for (int l = 0; l < m; ++l) { for (int p = 0; p < m; ++p) { d[i][j][p] = max(d[i][j][p], d[i-1][j][k] + d[1][k][l] + d[i-1][l][p]); } } } } } vector<vector<ll>> res(m, vector<ll>(m)); bool f = false; for (int i = 0; i < 35; ++i) { if (!((1LL<<i)&n)) continue; vector<vector<ll>> nres(m, vector<ll>(m)); for (int j = 0; j < m; ++j) { for (int k = 0; k < m; ++k) { for (int l = 0; l < m; ++l) { for (int p = 0; p < m; ++p) { if(f) nres[j][p] = max(nres[j][p], res[j][k] + d[1][k][l] + d[i][l][p]); else nres[j][p] = d[i][j][p]; } } } } f = true; swap(res, nres); } ll mx = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < m; ++j) { mx = max(mx, res[i][j]); } } cout << mx << endl; }