Balkan Olympiad in Informatics 2003 Day 2 Problem 2
You have just opened a new bank account, where you will receive amounts in euro currency. When you opened the account, you had no euros in it and no lei in your possession (lei is the currency used in Romania). During each of the next N days, you will receive various amounts of euros; the amounts may be negative, in which case the total amount of euros in your account will decrease. It is possible for you to have a negative balance of euros in your account at times. At the end of each day, the bank allows you to convert the whole amount of euro in your account into lei. The daily exchange rate varies according to the following rule: during the Kth day, a euro can be exchanged for K lei. The bank also charges you T lei for each conversion. Therefore, if at the end of day K you have S euros in your account, and you decide to convert them, you will receive S*K-T lei (of course, S can be negative). At the end of day N, you must convert your remaining euros into lei, even if the amount is non-positive.
Your objective is to maximize the final amount of lei you have at the end of the N-day period.
The first line of the input file euro.in contains two integers, N and T, separated by blanks. The next line contains N integers, specifying the amount of euros you will receive at the beginning of each day.
OutputThe output file should contain a single line, with the maximum amount of lei you can obtain.
7 1 -10 3 -2 4 -6 2 3
At the end of the first day, you exchange the -10 euros you have received for -11=-10*1-1 lei. The second conversion takes place at the end of the 5th day, when you have -1 euros in your account (3-2+4-6). The amount of lei you gain is -6=(3-2+4-6)*5-1. You make the last conversion at the end of the 7th day, using the last 5 euros in your account (2+3). The amount of lei you gain is 34=(2+3)*7-1. The final amount of lei is 17=-11-6+34.