Sane's Monthly Algorithms Challenge: November 2008

Stock Market II (Junior Level)

You have illegally obtained some insider information about the projected trend of a particular stock over the next 24 hours. With this information, you plan to repeatedly buy and sell the stock according to what will rake in the most profit.

The information consists of n values, each being the value of the stock at each time interval over a period of 24 hours. To buy one share of the stock, you must pay the value predicted for the current interval. To sell one share of the stock, you will receive the value predicted for that interval.

In the first Stock Market Challenge (July's SMAC Challenge), you were attempting to avoid rousing suspicion with your 1000 shares by only making one transaction. But this time you will be greedy: You may buy and sell the 1000 shares an unlimited number of times throughout the day (as long as you do not have more than 1000 in your holding at any one moment).

However, you will also need to pay a fixed commission rate to your broker on each transaction (every buy and every sell).

Using the stock’s projection, determine the optimum times to buy then sell, and the resulting maximum profit. It is always guaranteed that a profit can be made.

Input

On the first line is the integer n (2 ≤ n ≤ 1,000,000), and the fixed integer amount of commission per transaction.

On the next n lines are the prices for the i^th time intervals (1 ≤ i ≤ n). Each line contains a floating point number with no more than 2 decimal places, representing the share’s price for the i^th time interval.

Output

Output the maximum possible integer profit made in dollars, respectively.

Grading:

For 10 of the 15 test files, there will be no commission.

Sample Input

24 30
1.00
1.05
1.06
1.07
1.03
0.98
0.99
1.01
1.09
1.14
1.13
1.12
1.11
1.10
1.09
1.08
1.07
1.06
1.05
1.04
1.03
1.02
1.01
1.00

Sample Output

110

Explanation of Sample Data

1)  Buy  1000 at 1.00 for - 1000 - 30 = - $1030
4)  Sell 1000 at 1.07 for + 1070 - 30 = + $1040
6)  Buy  1000 at 0.98 for - 980  - 30 = - $1010
10) Sell 1000 at 1.14 for + 1140 - 30 = + $1110
                                        -------
                                           $110

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Jan 15, 2009
Author: DrSane

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)