問題一覧 > 通常問題

No.1536 Starting Over

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （AC するまで非表示） / 解いたユーザー数 38
作問者 : 57tggx / テスター : logx Re_menal2 ゅゅ pepper_aobuta
お気に入りにしたユーザー ProblemId : 6144 / 自分の提出
問題文最終更新日: 2021-05-21 14:02:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
ゅゅちゃんお誕生日コンテスト (順位表) の他の問題:

Problem Statement

$ N $ balls are arranged in a row, and the $ i $-th ball from the left ( $ 1 \leq i \leq N $ ) initially has the integer $ A_i $ written on it.

Yuyu can insert a total of $ M $ partitions into a total of $ (N + 1) $ places, consisting of the $ (N - 1) $ gaps between adjacent balls, the place immediately to the left of the leftmost ball, and the place immediately to the right of the rightmost ball. Multiple partitions may be inserted into the same place.

After the $ M $ partitions are inserted, the score is calculated as follows.

  1. For each partition, in order, perform the following operation: for all balls to the right of the partition, rewrite the integer $ X $ written on the ball to $ -X $, the value obtained by multiplying it by $ -1 $.
  2. The score is the sum of the integers written on the balls.

Output 1 way of inserting the partitions that maximizes the score. For the output,

  • the place immediately to the left of the leftmost ball is denoted by $ 0 $,
  • the gap between the $ i $-th ball and the $ i + 1 $-th ball from the left is denoted by $ i $,
  • the place immediately to the right of the rightmost ball is denoted by $ N $,
and you should output the place where each partition is inserted using this notation.

Input

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

Constraints:

  • All inputs are integers.
  • $ 1 \leq N \leq 2000 $
  • $ 1 \leq M \leq 2000 $
  • $ -10^9 \leq A_i \leq 10^9 $ ( $ i = 1, 2, \ldots, N $ )

Output

$T_1$
$T_2$
$\ldots$
$T_M$
Output $ M $ lines. On the $ j $-th line, output the place $ T_j $ (where $ 0 \leq T_j \leq N $ ) into which the $ j $-th partition is inserted. If there are multiple ways of inserting the partitions that maximize the score, you may output any of them. The order of $T_1, T_2, \ldots, T_M$ also does not matter.

Sample

Sample 1
Input
4 2
1 -2 -3 4
Output
1
3

Insert the $2$ partitions at position $ 1 $ and position $ 3 $ respectively, giving $1$ $|$ $-2$ $-3$ $|$ $4$. Multiplying the values written on all balls to the right of the $1$st partition by $-1$ gives $1$ $|$ $2$ $3$ $|$ $-4$, and then multiplying the values written on all balls to the right of the $2$nd partition by $-1$ gives $1$ $|$ $2$ $3$ $|$ $4$, so the score is $ 10 $. There is no way of inserting the partitions that achieves a larger score.

Sample 2
Input
3 1
3 -2 3
Output
3

Inserting a partition at position $3$ (to the right of the rightmost ball) gives a score of $4$, which is the maximum.

Sample 3
Input
3 2
2 3 4
Output
1
1

Multiple partitions may be inserted into the same place.

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