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.
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, E,..., E[N].
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.
I managed to solve the first subtask by employing a brute force solution (O(2^n)). But for the second and third subtasks I don't think that a brute force solution will be optimal.
Also, for the second subtask I have a vague idea. Taking X to be the number of trainings, then N-X is the number of battles. By maximizing experience gained from N-X battles, we might get the answer, but I'm not sure if it's the right way.
I do not have any idea of how to solve the 3rd Subtask without using a brute force algorithm. Help would be appreciated. Edit: Link to the above question in the IARCS website : https://www.iarcs.org.in/inoi/2017/