# include bits stdc using namespace std define MAXN 5100 define FOR for

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59``` ```#include using namespace std; #define MAXN 5100 #define FOR(s, e) for(int i=s; i (1 + 2)^3 int intPow(int x) { int d = 0; while(x != 0) { d += (x % 10); x = x / 10; } return (int)pow(d, 3); } //Precomputing training cost, i.e cost[i] for all i void preComp() { FOR(1, n) { cost[i] = cost[i - 1] + intPow(cost[i-1]); } } //f(i, j) denotes i_th city and j represents the amount of training done int f(int i, int j) { if(memo[i][j] != -1) return memo[i][j]; if(i == n) return 0; else { //We can either train in the city or we don't //i.e f(i+1, j+1) and f(i+1, j) //ATP, if we dont train then value add upto the XP //hence, f(i+1, j) + (cost[j] * xp[i]) //Max of the both decision is the answer memo[i][j] = max(f(i+1, j+1), f(i+1, j) + (cost[j] * xp[i])); } return memo[i][j]; } void solve() { //Input Start cin >> n >> cost[0]; FOR(0, n) { cin >> xp[i]; } //Input End preComp(); memset(memo, -1, sizeof(memo)); cout << f(0, 0) << endl; } int main() { __fastio; solve(); return 0; } ```