-----INOI 2017, Problem 2, Training-----
Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route
for the journey so that it passes through N cities, numbered 1, 2, …, N, and in this order.

When they set out, Pikachu has an initial strength of Sin as well as an experience
value (XV) of 0. As they travel they may increase his strength and experience value
in a manner to be described below.

In each city, Ash can choose either to train Pikachu or let Pikachu battle the
Gym-leader (but not both). The Gym-leader in ith city has experience E[i]. If
Pikachu enters a city i with strength S and decides to train, then this
increases his strength by the cube of the sum of the digits in his current
strength. For example, if he entered a city with a strength of 12, then
training will increase his strength to 12 + (1+2)3 = 39. On the other hand,
if he enters city i with strength S and battles the Gym-leader, then this
increases his experience value XV by S*E[i].

Ash wants your help to find out the maximum XV that Pikachu can attain
at the end of his journey.

-----Input-----
- The first line contains two space separated integers, N and Sin, which are the number of cities, and the initial strength, respectively.

• The second line contains N space separated integers, which correspond to E[1], E[2],..., E[N].

-----Output-----
- A single integer which is the maximum XV that Pikachu can attain.

-----Constraints-----
For all test cases you may assume that:

• 1 ≤ N ≤ 5000
• 0 ≤ Sin ≤ 109
• 0 ≤ E[i] ≤ 104

Subtask 1: For 10% of the score,

• N ≤ 20 and Sin = 1

Subtask 2: For further 40% of the score,

• E[i] = k for all i
  i.e. E[i] is some constant k, for all i

Subtask 3: For further 50% of the score,

• No further constraints.

-----Example-----
Input 1:
2 12
5 10

Output 1:
390

-----Explanation 1-----
Suppose Pikachu trains in the first city, his strength will increase to 39, because as explained above, 12 + (1+2)3 = 39. If he battles in the first city, his XV will increase by (12*5) = 60.

If Pikachu trains in the first city, and then battles in the second city, his XV will increase by 39*10 = 390. So, the final XV will be 0+390 = 390. You can check that you cannot do better than this. Hence the answer is 390.

Input 2:
4 1
100 1 6 2

Output 2:
120

-----Explanation 2-----
Pikachu battles in the first city, trains in the second and third, and then battles in the fourth city. So his strength going into each of the four cities is (1, 1, 2, 10). And so he gains 1100 XV from the first city and 102 XV from the fourth city. This gets him a total of 120 XV, and you can verify that nothing better can be done.

Note:
You may download the problem statements PDF and test cases zipped files here: http://pd.codechef.com/com/inoi/problems.zip. Please feel free to use them during the contest.
Password for the PDF and test cases zip files: DPtrumpsGreedy2017

见题面

见题面