結果
問題 |
No.3230 Mutual Corresponding System
|
ユーザー |
![]() |
提出日時 | 2025-07-14 20:19:59 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 232 ms / 2,000 ms |
コード長 | 980 bytes |
コンパイル時間 | 1,457 ms |
コンパイル使用メモリ | 87,848 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-07-16 15:14:42 |
合計ジャッジ時間 | 4,865 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
import std.stdio, std.algorithm, std.array, std.conv; void main() { auto NM = readln.split.to!(long[]); auto N = NM[0], M = NM[1]; auto T = readln.split.to!(long[]); long[][] A, P; foreach (_; 0 .. N) { auto row = readln.split.to!(long[]); A ~= row; P ~= new long[N]; } foreach (i; 0 .. N) foreach (j; 0 .. N) if (i == j) P[i][j] = 0; else P[i][j] = -long.max; long p = 1; while (p <= M) { if ((M&p) != 0) P = multiply(P, A); p *= 2; A = multiply(A, A); } foreach (i; 0 .. N) { long ans; foreach (j; 0 .. N) ans = max(ans, T[j] + P[j][i]); write(ans, " "); } writeln; } long inner_prod(long[] a, long[] b) { long c; foreach (i; 0 .. a.length) { c = max(c, a[i] + b[i]); } return c; } long[][] multiply(long[][] a, long[][] b) { long[][] c; const N = a.length; c.length = N; foreach (i; 0 .. N) { c[i].length = N; foreach (j; 0 .. N) foreach (k; 0 .. N) c[i][j] = max(c[i][j], a[i][k] + b[k][j]); } return c; }