結果
問題 | No.572 妖精の演奏 |
ユーザー |
![]() |
提出日時 | 2021-03-10 09:03:01 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 105 ms / 2,000 ms |
コード長 | 1,665 bytes |
コンパイル時間 | 2,189 ms |
コンパイル使用メモリ | 77,300 KB |
実行使用メモリ | 52,492 KB |
最終ジャッジ日時 | 2024-10-12 00:26:19 |
合計ジャッジ時間 | 4,865 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
import java.util.*;import java.io.*;public class Main {public static void main(String[] args) throws Exception{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));long n = Long.parseLong(br.readLine()) - 1;int m = Integer.parseInt(br.readLine());long[][][] values = new long[34][m][m];for (int i = 0; i < m; i++) {String[] line = br.readLine().split(" ", m);for (int j = 0; j < m; j++) {values[0][i][j] = Integer.parseInt(line[j]);}}for (int i = 1; i < 34; i++) {for (int j = 0; j < m; j++) {for (int k = 0; k < m; k++) {for (int l = 0; l < m; l++) {values[i][j][k] = Math.max(values[i][j][k], values[i - 1][j][l] + values[i - 1][l][k]);}}}}long[][] ans = new long[m][m];for (int i = 33; i >= 0 && n > 0; i--) {if (n < (1L << i)) {continue;}long[][] next = new long[m][m];n -= (1L << i);for (int j = 0; j < m; j++) {for (int k = 0; k < m; k++) {for (int l = 0; l < m; l++) {next[j][k] = Math.max(next[j][k], ans[j][l] + values[i][l][k]);}}}ans = next;}long max = 0;for (long[] arr : ans) {for (long x : arr) {max = Math.max(x, max);}}System.out.println(max);}}