No.664 超能力者Aと株価予測

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 34
作問者 : horiesinitihoriesiniti / テスター : 37zigen37zigen

0 ProblemId : 1211 / 出題時の順位表

問題文

A君は超能力者である。その日の一種類の株価を1分単位で予知できる。
A君の予知は絶対でありA君がどんな売買をしても値段が予知から外れることは絶対にない。

A君はその日のうちは予知できたその株だけを売買する。
A君は1分単位でその株を売買するか様子見をするかを選択する。
一日$M$回転でき、そのまま次の株購入に投入できる。
23:00追記 回転とは、(ここでは)株を売って、1株あたりそのタイミングの株価の値段で資金と交換し、手元資金を得る行為とします。

A君の最初の手元資金$K$、予知した株価のデータ、回転できる回数$M$が与えられるので、市場が終わった時のA君の手元資金の最大値を求めよ。


条件は以下の通り。
株は一株単位で売買できる。
9時から最大で15時30分まで開かれ、1分単位で売買される(つまり株価データは最大で391件)。
売買手数料は0円としてよい。
市場が終了したあとに手元に残った株は資金と交換できない。

入力

$N$ $M$ $K$
$A_1$
$\dots$
$A_{N+1}$

市場の開かれる時間$N$分、回転できる回数$M$、A君の手元資金$K$が与えられる。
$1 \le N \le 390$
$1 \le M \le 20$
$1 \le k \le 10000$
$100 \le A_i \le 300$

$N$=1なら市場は9時から9時1分まで開かれ2回売買のチャンスがある。
$N$=70なら市場は9時から10時10分まで開かれる。
$M$=1なら1日に1回買うことと1回売ることができる。$M=$iなら1日にi回買うこととi回売ることができる。

続く$N+1$行にわたり1分単位の株価$A_i$が与えられる。)。
与えられるデータは全て自然数と仮定してよい。

出力

手元資金が最大になるように売買した時の市場終了後の手元資金の最大値を一行に出力すること。
最後に改行してください。

サンプル

サンプル1
入力
10 3 2000
200
190
180
170
160
150
150
140
130
120
110
出力
2000

今日は一日中株価が下がりつづけ一度も売買しないのが賢明な判断なようだ。 よって最初の手元資金がそのまま答えである。

サンプル2
入力
10 3 2000
100
110
120
130
140
150
160
170
180
190
200
出力
4000

その日はひたすら値上がりし続けた。9時の値段で買って、9時10分の値段で売却すればよい。

サンプル3
入力
21 5 3000
150
144
133
130
127
129
138
142
131
131
126
126
133
135
121
115
122
130
124
110
138
134
出力
5052

A君は賢く売買して最大の利益を上げた。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。