UVa 11136: Hoax or what is a simulation problem using multisets. Conceivably this problem could also be solved with vectors or arrays, however since the contents of the data structure is so dynamic, a multiset is faster. This is because multiset inserts and deletes can be done in O(logn), and a multiset is automatically kept in sorted order, so accessing the elements we care about is O(1). I made two implementation mistakes when writing this solution. First, note that the problem statement says that no bill is greater than 10^6. I thought this meant I was ok to use ints everywhere, but I was wrong! Since the promotion can be at most 5000 days, the largest possible value of the promotion is 5000 * 10^6 = 5 * 10^9, which is bigger than the size of an int. I also absent-mindedly put the line of code that removed items from the multiset before the line that added them to the total, which was not correct.