I need to fight N monsters whose energy is given by the array Arr[1:n]. I need to maximize my glory points which are defined as the net number of battles won. Initially, I have Energy E and 0 glory points. I must battle the monsters sequentially from left to right in a queue. I have the following 4 options: 1. If my current energy is greater than the monster's energy I can defeat it and lose energy equal to that of the monster's energy and gain a glory point. 2. I may choose not to compete with the monster. Then neither my energy nor my glory point changes. 3. I may delay my encounter with the monster by sending him to the back of the queue. Then neither my energy nor my glory point changes. 4. I may lose to the monster to gain its energy but lose a glory point. My energy should always be greater than 0. And glory points at all times greater than or equal to 0. Find the maximum value of glory points. Constraints: 1=<N<=1000 1<=E<=10^6 1<=Arr[i]<=10^6

A clarification. If energy of monster you're battling with is lesser than your energy, still you can choose to lose from that monster to gain its energy. Am I correct?

Yes you can

If that is true, then notice that due to sending a monster at the back of the queue option, you can fight the monsters in any order (which is easy to prove).

Sort all the monsters on the basis of energies. Fix the number of monsters you lose to. Call it $$$k$$$. It is optimal that you lose to $$$k$$$ monsters with highest energies (suffix of length $$$k$$$ in the sorted list).

It is optimal to win against some prefix of monsters in the list. For every $$$k$$$, find the highest $$$j$$$ such that $$$j \le n-k$$$ and $$$sum[1..j] \le sum[n-k+1..n] + E$$$. Note that $$$sum[i..j]$$$ denotes the sum of energies of monster from $$$[i..j]$$$ in the sorted list. You score for that $$$k$$$ is $$$j-k$$$.

Do this for all possible $$$k$$$ and find maximal score. You may use binary search for that.

Can you give a proof that the monsters can be ordered in any possible way we want

Let's say you have

monsters left at a given point —m, and you want to battle monstera_1, a_2, ... a_m. You can send all monsters froma_itoa_1to the back so that nowa_i-1is the first monster in the queue. You can fight it now.a_iThe same can now be applied to remaining monsters.

I don't think we need to select k monsters to defeat just maintain a multiset keep eliminating the lowest monster until you can, update the answer with current points and then lose by the most powerful monster. this easily works in O(nlogn), and log factor can be further improved by 2 pointers.