Problem
バッタは、同じ線上にある等距離にある列にジャンプします。列には 1 から N までのシリアル番号が付いています。最初に、バッタは番号 1 の柱に座っています。現在のバーから数えて、1 から K バーまで前方にジャンプできます。
各列で、バッタは数枚の金貨を獲得または失う可能性があります (この数は各列で既知です)。より多くの金貨を集めるために、バッタがどのようにジャンプする必要があるかを決定します。バッタは後ろにジャンプできないことに注意してください。
入力:
- 最初の行には、N と K という 2 つの自然数が含まれています (\(2 <= N ,\ K < = 10000\))、スペース区切り;
- 2 行目では、スペースで区切られた N-2 個の整数です。バッタが各列で取得するコインの数 (2 番目から N-1 番目まで)。この数値がマイナスの場合、バッタはコインを失います
。
モジュロのすべての数値が 10000 を超えないことが保証されます。
出力:
- 最初の行で、プログラムはバッタが収集できるコインの最大数を表示する必要があります。
- 2 行目は、Grasshopper のジャンプ数を表示します。
- 3 行目 – Grasshopper が訪問するすべての列の番号 (昇順にスペースで区切られます)
正解が複数ある場合は、いずれかを出力します。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
5 3
2 -3 5
|
7
3
1 2 4 5
|