No.572 妖精の演奏
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 82
作問者 :
horiesiniti
/ テスター :
はむこ
タグ : / 解いたユーザー数 82
作問者 :
horiesiniti
/ テスター :
はむこ
問題文最終更新日: 2017-10-06 23:04:16
問題文
妖精が譜面に従って演奏をします。 音符が一個ずつならんだ譜面で、ある音の次にある音をならすと一定のスコアが手に入ります。 譜面に書くべき音符の数n個と音の種類数ｍ、ある音の次にある音を鳴らすといくらのスコアが加算されるかの表が与えられます。 この二つのデータから最大スコアとなる譜面を書いたときのスコアを求めて下さい。 譜面の評価はスコアの単純合計です。
入力
$n$
$m$
$A_{11}$$\dots$$A_{1m}$
$\dots$
$A_{m1}$$\dots$$A_{mm}$
$1 \leq n \leq 5 \times 10^{9}$
$2 \leq m \leq 30$
$0 < A_{i,j} \leq100$
$A_{i,j}$はi種類目の音の後にj種類目の音を鳴らすと$A_{i,j}$点のスコアが入るという意味である。
ただし妖精は同じ音の連続を嫌うので$A_{i,i}$=0
$A_{i,j}$は整数と仮定してよい。
出力
最後に改行してください。
サンプル
サンプル1
入力
7 4 0 20 10 100 10 0 100 10 100 10 0 10 10 100 20 0
出力
600
1 4 2 3の音の繰り返しである。
サンプル2
入力
177 10 0 1 2 9 10 10 6 7 10 5 4 0 5 3 5 1 4 4 10 4 8 7 0 8 2 5 5 2 6 6 8 7 3 0 5 1 6 5 8 2 1 6 1 7 0 9 8 5 3 5 1 2 7 4 9 0 10 5 5 9 3 3 8 6 8 8 0 9 2 10 2 5 7 7 1 9 7 0 6 10 9 1 4 4 5 7 6 4 0 3 1 4 3 8 4 9 1 1 3 0
出力
1702
サンプル3
入力
123 12 0 45 21 74 60 97 45 10 71 70 76 8 57 0 1 13 49 23 61 58 52 35 39 34 89 53 0 95 86 61 72 98 88 78 47 77 66 7 42 0 25 14 23 11 25 34 94 53 60 57 41 16 0 86 10 23 64 23 53 76 78 7 48 37 30 0 18 87 73 7 51 31 99 57 65 96 83 36 0 73 33 84 28 74 69 59 62 47 6 33 55 0 19 13 34 25 14 32 97 17 47 20 46 23 0 58 32 68 28 50 74 74 32 25 63 84 41 0 80 20 44 42 1 95 68 32 8 1 71 91 0 11 54 86 48 84 53 80 48 45 5 90 26 0
出力
11532
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。