For problem 1241C. Legacy tut.
Here's another idea to solve it in linear time. Whole idea is to become a thug seller, haha! You sell ticket, but you can take it back! Any time! But respect police, ah? So whenever you take ticket back, you return funds. Otherwise you'll never reach k.
Idea
This is how whole thing works. OK, we also swap x and y, so x is always better.
- All non-x and non-y buyers should wait. You respect their.. booking, but kindly ask them to quit the line. They will get their tickets after you deal with X and Y. Besides those guys will get best price.
- So, you start selling X, or Y. Whatever it is, you sell most expensive remaining ticket. AND.. if at some point you've just realized, that you could sell even more expensive ticket, but it is sold with lower profit, you just take it back, (give money back) and sell it again with better profit. Buyer who just suffered lose of ticket is to be calmed by buying another (probably cheaper) one.