No.664 Psychic A and Stock Price Prediction
タグ : / 解いたユーザー数 76
作問者 :
horiesiniti
/ テスター :
37zigen
Problem Statement
A-kun is a psychic. He can foresee the price of one kind of stock for that day, minute by minute.
A-kun's foresight is absolute, and no matter how he trades, the price will never deviate from what he foresaw.
During that day, A-kun trades only the stock he foresaw.
Each minute, A-kun chooses whether to trade the stock or to wait and watch.
He can make $M$ turnovers per day, and the proceeds can be put straight into the next stock purchase.
Added at 23:00: A turnover (here) means the act of selling shares, exchanging them for funds at the stock price at that moment per share, and thereby obtaining funds on hand.
Given A-kun's initial funds on hand $K$, the foreseen stock price data, and the number of turnovers $M$ he can make, find the maximum value of A-kun's funds on hand when the market closes.
The conditions are as follows.
The stock can be bought and sold in units of one share.
The market is open from 9:00 until at most 15:30, and trading takes place in units of one minute (that is, there are at most 391 stock price entries).
You may assume trading fees are 0 yen.
Shares left in hand after the market closes cannot be exchanged for funds.
Input
$N$ $M$ $K$
$A_1$
$\dots$
$A_{N+1}$
The number of minutes $N$ the market is open, the number of turnovers $M$ he can make, and A-kun's funds on hand $K$ are given.
$1 \le N \le 390$
$1 \le M \le 20$
$1 \le k \le 10000$
$100 \le A_i \le 300$
If $N$=1, the market is open from 9:00 to 9:01, and there are 2 chances to trade.
If $N$=70, the market is open from 9:00 to 10:10.
If $M$=1, he can buy once and sell once per day. If $M=$i, he can buy i times and sell i times per day.
The following $N+1$ lines give the stock price $A_i$ for each minute.)
You may assume that all given data are natural numbers.
Output
Output on one line the maximum value of the funds on hand after the market closes when trading so as to maximize the funds on hand.
Print a newline at the end.
Sample
Sample 1
Input
10 3 2000 200 190 180 170 160 150 150 140 130 120 110
Output
2000
Today the stock price keeps falling all day, so it seems the wise decision is not to trade even once. Therefore, the initial funds on hand are the answer as they are.
Sample 2
Input
10 3 2000 100 110 120 130 140 150 160 170 180 190 200
Output
4000
The price kept rising throughout the day. He should buy at the 9:00 price and sell at the 9:10 price.
Sample 3
Input
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
Output
5052
A-kun traded wisely and made the maximum profit.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。