Codeforces - C2. Potions (Hard Version)
Problem Link Algorithm used - Greedy, Data structures Time Complexity: O(N log N) You start out with a health value of 0. There are N potions numbered 1 to N that are examined sequentially. You may choose either drink or not drink a potion. Upon drinking a potion your health value changes by the potion's value. If the potion's is positive, then your health value increases by the potion's value. But if it's negative then your health value decreases by the potion's value. You must ensure that your health value remains non-negative. Find the maximum number of potions that you can drink. It is obvious that you can drink all potions whose values are greater than or equal to 0, since your health value will never dip below 0 upon drinking these. To maximize the answer, we should also try to drink some negative potions. To try and drink the maximum number of potions with a negative value, we sort them in ascending order and iterate over them. For each potion, check if our...