No.1536 仕切り直し
タグ : / 解いたユーザー数 35
作問者 :
57tggx
/ テスター :
logx
Re_menal2
ゅゅ
pepper_aobuta
問題文
$ N $ 個のボールが一列に並んでおり， 左から $ i $ （ $ 1 \leq i \leq N $ ）番目のボールにははじめ整数 $ A_i $ が書かれています．
ゅゅさんは， 隣り合うボールのすき間 $ (N - 1) $ 箇所・ 左端のボールの左隣・ 右端のボールの右隣をあわせた 合計 $ (N + 1) $ 箇所に， 全部で $ M $ 枚の仕切りを入れることができます． 同じ場所に複数枚の仕切りを入れることも可能です．
$ M $ 枚の仕切りを入れた後， 以下の方法で得点が計算されます．
- 各仕切りについて，順に次の操作を行う： 仕切りより右にある 全てのボールに書かれた整数 $ X $ を， $ -1 $ をかけた値 $ -X $ に書き換える．
- ボールに書かれた整数の総和を，得点とする．
得点を最大化するような仕切りの入れ方を 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もしくは右上の雲マークをクリックしてアカウントを作成してください。