問題一覧 > 通常問題

No.1536 仕切り直し

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 26
作問者 : 57tggx57tggx / テスター : logxlogx Re_menal2Re_menal2 ゅゅゅゅ pepper_aobutapepper_aobuta
0 ProblemId : 6144 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-21 14:02:07

問題文

$ N $ 個のボールが一列に並んでおり, 左から $ i $ ( $ 1 \leq i \leq N $ )番目のボールにははじめ整数 $ A_i $ が書かれています.

ゅゅさんは, 隣り合うボールのすき間 $ (N - 1) $ 箇所・ 左端のボールの左隣・ 右端のボールの右隣をあわせた 合計 $ (N + 1) $ 箇所に, 全部で $ M $ 枚の仕切りを入れることができます. 同じ場所に複数枚の仕切りを入れることも可能です.

$ M $ 枚の仕切りを入れた後, 以下の方法で得点が計算されます.

  1. 各仕切りについて,順に次の操作を行う: 仕切りより右にある 全てのボールに書かれた整数 $ X $ を, $ -1 $ をかけた値 $ -X $ に書き換える.
  2. ボールに書かれた整数の総和を,得点とする.

得点を最大化するような仕切りの入れ方を 1 つ出力してください.出力にあたっては,

  • 左端のボールの左隣を $ 0 $
  • 左から $ i $ 番目のボールと $ i + 1 $ 番目のボールの間の すき間を $ i $
  • 右端のボールの右隣を $ N $
で表し,それぞれの仕切りを入れる場所を出力してください.

入力

$N\ M$
$A_1\ A_2\ \ldots\ A_N$

制約:

  • 入力はすべて整数
  • $ 1 \leq N \leq 2000 $
  • $ 1 \leq M \leq 2000 $
  • $ -10^9 \leq A_i \leq 10^9 $ ( $ i = 1, 2, \ldots, N $ )

出力

$T_1$
$T_2$
$\ldots$
$T_M$
$ M $ 行に分けて出力してください. $ j $ 行目には, $ j $ 番目の仕切りを入れる場所 $ T_j $ (ただし $ 0 \leq T_j \leq N $ )を出力してください. 得点を最大化する仕切りの入れ方が複数あるときは,どれを出力してもかまいません.また, $T_1, T_2, \ldots, T_M$ の順番も問いません.

サンプル

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

$2$ 枚の仕切りをそれぞれ位置 $ 1 $ と位置 $ 3 $ に入れて $1$ $|$ $-2$ $-3$ $|$ $4$ とします. $1$ 枚目の仕切りより右にある全てのボールに書かれている値に $-1$ をかけると $1$ $|$ $2$ $3$ $|$ $-4$ となり, 次に $2$ 枚目の仕切りより右にある全てのボールに書かれている値に $-1$ をかけると $1$ $|$ $2$ $3$ $|$ $4$ となるので, 得点は $ 10 $ となります. これより大きな得点を実現する仕切りの入れ方は存在しません.

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

位置 $3$ (右端のボールの右)に仕切りを入れると 得点は $4$ となり,これが最大です.

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

同じ場所に仕切りを複数枚入れることも可能です.

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