問題一覧 > 通常問題

No.489 株に挑戦

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 163
作問者 : 小指が強い人小指が強い人 / テスター : tanzakutanzaku
4 ProblemId : 1266 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-02-26 22:33:34

問題文

親指君は、YC株式会社の株を$K$株買ってその後時間経ってから売って、儲けようと思っています。
親指君は超能力者なので、現在から$N-1$日目以内までなら$i$日目が1株あたり$x_i$円あることを確実に予測できます。
しかし、株を保有する期限は買ってから$D$日後までであり、その間に売らなければなりません。
利益を最大にするには、現在から何日目に株を買って何日目に売ればいいでしょうか。
ただし、株の買い売りは1回のみとします。

入力

$N$ $D$ $K$
$x_0$
$x_1$
︙
$x_{N-1}$

$2\ \le\ N\ \le\ 10^5$ (整数)
$1\ \le\ D\ <\ N$ (整数)
$1\ \le\ K\ \le\ 10^6$ (整数)
$1\ \le\ x_i\ \le\ 10^6$ (整数)
$i=0,1,...,N-1$

出力

$MAX$
$j\ \ k$
1行目に最大の利益を出力してください。32bit整数では収まらない場合があるので注意してください。
2行目に買う日($j$日目)と売る日($k$日目)を間に空白を空けて出力してください。
$j$と$k$が複数ある場合は、辞書順で最初にあるものを出力してください。
利益を得ることが出来ない場合やマイナスになる場合は、$0$のみを一行出力してください。

サンプル

サンプル1
入力
7 2 1000
1
3
5
1
4
4
7
出力
4000
0 2

0日目と2日目の1株あたりの値段の差は4円です。
親指君は1000株買ったので答えは$4×1000=4000$円です。
3日目と6日目の組が最大のように見えますが、買ってから2日後以内に売らなければなならないので、6日目に売ることはできません。

サンプル2
入力
5 4 100
1
2
1
2
1
出力
100
0 1

$(j,k)$で表す時、利益が最大である組は$(0,1),(0,3),(2,3)$です。
辞書順で最初の組を選択するので$(0,1)$となります。

サンプル3
入力
5 1 100
5
4
3
3
1
出力
0

1株あたりの値段が減少するか変化なしなので利益を得ることが出来ません。
したがって、$0$を出力してください。

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