No.1536 仕切り直し

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1536 仕切り直し

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題（複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 36
作問者 :

57tggx / テスター :

logx

Re_menal2

ゅゅ

pepper_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$ 枚の仕切りを入れた後，以下の方法で得点が計算されます．

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

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

左端のボールの左隣を $0$
左から $i$ 番目のボールと $i + 1$ 番目のボールの間のすき間を $i$
右端のボールの右隣を $N$

で表し，それぞれの仕切りを入れる場所を出力してください．

入力

 $N M$ 
 $A_{1} A_{2} \dots A_{N}$

制約：

入力はすべて整数
$1 \leq N \leq 2000$
$1 \leq M \leq 2000$
$- 10^{9} \leq A_{i} \leq 10^{9}$ （ $i = 1, 2, \dots, N$ ）

出力

 $T_{1}$ 
 $T_{2}$ 
 $\dots$ 
 $T_{M}$

M

行に分けて出力してください．

j

行目には，

j

番目の仕切りを入れる場所

T_{j}

（ただし

0 \leq T_{j} \leq N

）を出力してください．得点を最大化する仕切りの入れ方が複数あるときは，どれを出力してもかまいません．また，

T_{1}, T_{2}, \dots, 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$ （右端のボールの右）に仕切りを入れると得点は $4$ となり，これが最大です．

サンプル3

入力

3 2
2 3 4

出力

1
1

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

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

yukicoder

No.1536 仕切り直し

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力