結果
問題 | No.572 妖精の演奏 |
ユーザー |
![]() |
提出日時 | 2017-10-09 23:09:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,951 bytes |
コンパイル時間 | 998 ms |
コンパイル使用メモリ | 102,700 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-17 07:08:30 |
合計ジャッジ時間 | 1,722 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <cmath>#include <vector>#include <list>#include <map>#include <set>#include <functional>#include <queue>#include <iostream>#include <string.h>#include <iomanip>#include <algorithm>#include <functional>#include <cstdint>#include <climits>#include <unordered_set>#include <sstream>#include <stack>using namespace std;typedef long long int ll;typedef pair<ll,ll> pii;typedef tuple<ll,ll,ll> t3;using namespace std;ll n, m;vector<vector<vector<ll>>> mat;vector<vector<ll>> add(const vector<vector<ll>>& s){auto p = vector<vector<ll>>(m, vector<ll>(m, 0));for(int y1 = 0;y1 < m;y1++){for(int x1 = 0;x1 < m;x1++){for(int y2 = 0;y2 < m;y2++){p[y1][x1] = max(p[y1][x1], s[y2][x1] + s[y1][y2]);}}}return p;}vector<vector<ll>> add(const vector<vector<ll>>& l,const vector<vector<ll>>& r){auto p = vector<vector<ll>>(m, vector<ll>(m, 0));for(int y1 = 0;y1 < m;y1++){for(int x1 = 0;x1 < m;x1++){for(int y2 = 0;y2 < m;y2++){p[y1][x1] = max(p[y1][x1], l[y2][x1] + r[y1][y2]);}}}return p;}int main() {cin >> n >> m;mat.emplace_back();mat[0].assign(m, vector<ll>(m, 0));for(int y = 0;y < m;y++){for(int x = 0;x < m;x++){cin>> mat[0][y][x];}}for(int i = 1, j = 1;j <= n;i++, j*=2){mat.emplace_back(add(mat[i-1]));}auto ret = vector<vector<ll>>(m, vector<ll>(m, 0));int i = 0;n--;while(n > 0){if(n & 1){ret = add(ret, mat[i]);}n>>=1;i++;}ll r = 0;for(int y = 0;y < m;y++){for(int x = 0;x < m;x++){r = max(r, ret[y][x]);}}cout << r << endl;return 0;}