問題一覧 > 通常問題

No.258 回転寿司(2)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 194
作問者 : yuki2006yuki2006
3 ProblemId : 710 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:53

問題文

あなたは、回転寿司にきている。
お寿司はN皿が順番に流れてくる。N皿のお寿司のそれぞれの美味しさが\(V_i\)で表される。

流れてくるお寿司が自分の前に来た時に取ることができるが、このお店のルールで、
連続で皿を取ることが出来ない。
もちろん、自分の前を過ぎたお寿司も取ることが出来ない。

この時、あなたが得られる美味しさの最大の合計値と取ったお皿の番号（1から始まる番号）を昇順に求めてください。
お寿司は一周回ってくることはないとする。

入力

\(N \)
\(V_1\,V_2\,V_3 \ldots V_N \)

1行目に、お寿司の数\(N (1\le N \le 1000)\)が与えられます。
2行目に、$i$番目のお寿司の美味しさ \( V_i (1\le V_i \le 100,1 \le i \le N) \)が半角スペース区切りで与えれれます。

出力

1行目にあなたが得られる美味しさの最大の合計値と
2行目に取ったお皿の番号(1-index)を空白区切りで出力してください。
答えが複数ある場合、どれか一つを出力してください。
答えが1つもない場合は、好きなお寿司を食べても良い。

サンプル

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

お寿司の取り方は、「1個目と３個目」のお寿司を取る、「１個目と４個目」のお寿司を取る、または「２個目と4個目」のお寿司を取る方法があるが、
２個目、４個目のお寿司を取ることで、最大の美味しさが得られる。

サンプル2
入力
4
5 4 4 9
出力
14
1 4

1個目のお寿司と4個目のお寿司を取ることで最大の美味しさの合計が得られる。

サンプル3
入力
7
1 2 9 10 1 1 4
出力
16
2 4 7

2,10,4と取れば最大の16が得られる。
10の後の6番目の１をあえてスルーしないといけない。

サンプル4
入力
1
100
出力
100
1

1皿しかない場合もあります。

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