問題一覧 > 通常問題

No.1360 [Zelkova 4th Tune] 協和音

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 179
作問者 : 👑 KazunKazun / テスター : Kanten4205Kanten4205
1 ProblemId : 5221 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-22 23:05:02

注意

yukicoder contest 279 (Zelkova and Cherry) の問題は 難易度順に並んではいない. よって, 問題文や難易度を表すの星の数, 正解者数等といった公開されている情報から問題を取捨選択することを強く推奨する.

お知らせ

判定結果のなかに, QLE が含まれている場合, 想定解またはジャッジコードに誤りが含まれいている可能性が大きいので, すぐに報告してください.

問題文

$N$ 種類の音 $1,\dots,N$ について, 音 $i$ を鳴らすと,音の得点として $A_i$を得る. また, 2つ以上の音を同時に鳴らすと, その音の得点の総和を得るが, その得点に加え, 音 $i, j$ を同時に鳴らしていたとき, そしてそのときに限り, 得点として更に $B_{i,j}$ だけ得る ($B_{i,j} < 0$ の場合もあり得る). $N$ 種類の音から1個以上の任意個の音を同時に鳴らしたとき, 得点の最大値とそれを達成する音の鳴らし方を求めよ.

制約

  • $1 \leq N \leq 18$
  • $0 \leq A_i \leq 10^9$
  • $-10^9 \leq B_{i,j} \leq 10^9$
  • $B_{i,i}=0\ (i=1,\dots,N)$
  • $B_{i,j}=B_{j,i}\ (i,j=1,\dots,N)$
  • 入力は全て整数である.

入力

入力は以下の形式で標準入力から与えられる.
$N$
$A_1\ \dots\ A_N$
$B_{1,1}\ \dots \ B_{1,N}$
$\vdots$
$B_{N,1}\ \dots \ B_{N,N}$

出力

$K (\geq 1)$ 種類の音 $j_1,\dots,j_K$ を鳴らした時に得点が最大値であり, その得点が $W$ であるとき, 以下のように出力せよ.

$W$
$j_1\ \dots j_K$

ただし, $j_1,\dots,j_K$ のなかに同じ音の番号を2つ以上含んでいてはいけない. また, 得点を最大にする音の鳴らし方が複数ある場合, どれを出力しても構わない. そして, 最後に改行することを忘れないこと. (2021/01/22 23:04 数字 $\to$ 音の番号に訂正)

サンプル

サンプル1
入力
2
2 3
0 -4
-4 0
出力
3
2

  • 音 $1$ のみを鳴らした場合...得点は2点
  • 音 $2$ のみを鳴らした場合...得点は3点
  • 音 $1,2$ を同時に鳴らした場合...得点は3+2+(-4)=1点
よって, 音 $2$ のみを鳴らして 3点得るのが最大である.

サンプル2
入力
3
10 20 30
0 -2 3
-2 0 -5
3 -5 0
出力
56
1 2 3

全部同時に鳴らすのが最大である. このとき, 得点は10+20+30+(-2+3-5)=56点になる.

サンプル3
入力
4
1 1 1 1
0 -10 -10 -10
-10 0 -10 -10
-10 -10 0 -10
-10 -10 -10 0
出力
1
1

2種類以上の音を同時にならすと, 得点が負になる. 従って,1種類のみを鳴らせば良い. また, 1種類のみであれば, どの音でもよい.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。