No.489 Challenge the Stock Market
小指が強い人
tanzakuProblem Statement
Oyayubi-kun wants to make a profit by buying $K$ shares of YC Corporation stock and selling them some time later.
Since Oyayubi-kun is a psychic, he can predict with certainty that on day $i$ the price is $x_i$ yen per share, for days up to day $N-1$ from now.
However, the stock can only be held for up to $D$ days after buying it, and it must be sold within that period.
To maximize the profit, on which day from now should he buy the stock, and on which day should he sell it?
Note that he buys and sells only once.
Input
$N$ $D$ $K$
$x_0$
$x_1$
︙
$x_{N-1}$
$2\ \le\ N\ \le\ 10^5$ (integer)
$1\ \le\ D\ <\ N$ (integer)
$1\ \le\ K\ \le\ 10^6$ (integer)
$1\ \le\ x_i\ \le\ 10^6$ (integer)
$i=0,1,...,N-1$
Output
$MAX$ $j\ \ k$On the first line, output the maximum profit. Note that it may not fit in a 32-bit integer.
On the second line, output the day to buy (day $j$) and the day to sell (day $k$), separated by a space.
If there are multiple pairs of $j$ and $k$, output the lexicographically first one.
If no profit can be made or the profit would be negative, output only $0$ on a single line.
Sample
Sample 1
Input
7 2 1000 1 3 5 1 4 4 7
Output
4000 0 2
The difference in price per share between day 0 and day 2 is 4 yen.
Since Oyayubi-kun bought 1000 shares, the answer is $4×1000=4000$ yen.
The pair of day 3 and day 6 may look like the maximum, but since he must sell within 2 days after buying, he cannot sell on day 6.
Sample 2
Input
5 4 100 1 2 1 2 1
Output
100 0 1
Written as $(j,k)$, the pairs with the maximum profit are $(0,1),(0,3),(2,3)$.
Since the lexicographically first pair is chosen, the answer is $(0,1)$.
Sample 3
Input
5 1 100 5 4 3 3 1
Output
0
The price per share only decreases or stays the same, so no profit can be made.
Therefore, output $0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。