結果
問題 | 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;}