結果
問題 | No.572 妖精の演奏 |
ユーザー |
|
提出日時 | 2021-05-05 00:37:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 893 bytes |
コンパイル時間 | 2,104 ms |
コンパイル使用メモリ | 197,696 KB |
最終ジャッジ日時 | 2025-01-21 07:01:05 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; int n, m; long long sum[36][30][30]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { cin >> sum[0][i][j]; } } for (int k = 1; k < 36; k++) { for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { for (int l = 0; l < m; l++) sum[k][i][j] = max(sum[k][i][j], sum[k-1][i][l] + sum[k-1][l][j]); } } } vector<long long> cur(m); --n; for (int k = 35; k >= 0; k--) { if (n & 1LL << k) { n -= 1LL << k; vector<long long> nxt(m); for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { nxt[j] = max(nxt[j], cur[i] + sum[k][i][j]); } } cur = nxt; } } cout << *max_element(cur.begin(), cur.end()) << endl; return 0; }