## Editorial for UTS Open '18 P4 - Ianine's Lil Lab

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: PlasmaVortex

Each coupon has a pair , the number of keyboard and monitors that it can buy. coupons cannot buy anything, and can be ignored. and coupons should always be used to buy keyboards, while and should be used for monitors. When deciding how to spend the coupons, first count how many keyboards and monitors you will get from the and coupons, then use any coupons for the item that you have less of.

Time Complexity:

There are ways to spend each coupon, which makes ways in total. Loop through all possibilities and choose the best option.

Time Complexity:

First, group the coupons by value. For each group, sort them in order of decreasing (which is also increasing , since they have the same value). Then, the coupons at the front will have the highest , while the ones at the back have the highest . Suppose you use a coupon on monitors, and used another coupon after it for keyboards. If instead you used the first one for keyboards and the second for monitors, you would have gotten more monitors and keyboards. Therefore, you should never use a coupon for monitors when a coupon behind it is used for keyboards, because there will always be a better way to use the coupons. In other words, the optimal way to spend the coupons is to use the first for keyboards (for some , where is the size of the group of coupons with value ), and the last coupons on monitors.

Using a precalculated prefix sum array, we can loop through to find the best choice of in time. Do this for each group, and choose the group with the best final result.

Time Complexity: