結果
問題 | No.572 妖精の演奏 |
ユーザー |
|
提出日時 | 2017-11-21 15:28:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 1,224 bytes |
コンパイル時間 | 1,992 ms |
コンパイル使用メモリ | 193,696 KB |
最終ジャッジ日時 | 2025-01-05 04:16:24 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int MAXN = int(5e9); const int MAXM = 30; long long N; int M; int A[MAXM][MAXM]; long long dp[40][MAXM][MAXM]; long long dp2[MAXM]; signed main() { ios::sync_with_stdio(false); cin >> N; cin >> M; for (int i = 0; i < M; ++i) { for (int j = 0; j < M; ++j) { cin >> A[i][j]; } } memset(dp, 0xc0, sizeof(dp)); for (int i = 0; i < M; ++i) { dp[0][i][i] = 0; } for (int i = 0; i + 1 < 40; ++i) { for (int j = 0; j < M; ++j) { for (int k = 0; k < M; ++k) { for (int l = 0; l < M; ++l) { for (int m = 0; m < M; ++m) { dp[i + 1][j][m] = max(dp[i + 1][j][m], dp[i][j][k] + A[k][l] + dp[i][l][m]); } } } } } --N; for (int i = 0; i < 40; ++i) { if (~N >> i & 1LL) continue; static long long tmp[MAXM]; memset(tmp, 0xc0, sizeof(tmp)); for (int j = 0; j < M; ++j) { for (int k = 0; k < M; ++k) { for (int l = 0; l < M; ++l) { tmp[l] = max(tmp[l], dp2[j] + A[j][k] + dp[i][k][l]); } } } for (int j = 0; j < M; ++j) { dp2[j] = tmp[j]; } } cout << *max_element(dp2, dp2 + M) << endl; return 0; }