結果
問題 |
No.572 妖精の演奏
|
ユーザー |
![]() |
提出日時 | 2017-10-07 15:10:31 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 959 bytes |
コンパイル時間 | 679 ms |
コンパイル使用メモリ | 102,300 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 21:59:54 |
合計ジャッジ時間 | 1,446 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
void main(){ import std.stdio, std.string, std.conv, std.algorithm; long n; int m; rd(n); rd(m); auto c=new long[][](m, m); foreach(i; 0..m) c[i]=readln.split.to!(long[]); auto d=new long[][][](33, m, m); foreach(k; 0..33)foreach(i; 0..m)foreach(j; 0..m){ if(k==0){ d[k][i][j]=c[i][j]; }else{ foreach(_; 0..m) chmax(d[k][i][j], d[k-1][i][_]+d[k-1][_][j]); } } long mx=0; foreach(s; 0..m){ auto dp=new long[][](33, m); if((n-1)&1)foreach(j; 0..m) dp[0][j]=d[0][s][j]; foreach(k; 1..33)foreach(j; 0..m){ if((n-1)&(1L<<k)){ foreach(i; 0..m) chmax(dp[k][j], dp[k-1][i]+d[k][i][j]); }else{ dp[k][j]=dp[k-1][j]; } } chmax(mx, dp[32].maxElement); } writeln(mx); } void chmax(T)(ref T x, T y){ if(x<y) x=y; } void rd(T...)(ref T x){ import std.stdio, std.string, std.conv; auto l=readln.split; foreach(i, ref e; x){ e=l[i].to!(typeof(e)); } }