시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1 | 1 | 1 | 100.000% |
After falling for a large number of fake get-rich-quick schemes, Marika is in serious need for cash, and really needs a get-rich-quick scheme. Instead of listenting to the ideas of strangers, Marika asked her mathematically talented friend David for some help. David suggested the following scheme, based on a feature of certain credit cards, called cashback.
Cashback means that you earn a certain percentage of cash back on purchase you make, depending on the type of purchase. Formally, there are $n$ categories of merchandise. If you purchase merchandise from category $i$ for $x$ SEK, you earn $p_i \cdot x$ SEK back, up to some maximum limit $m_i$ in a single month. While this does not help you earn money (since $p_i < 1$), you realized that you can simply return any products you bought to the store to get the money back.
Things are made more difficult by the fact that a particular store will get suspicious if you return too many products per month. In store $i$, you can buy and return merchandise for at most $a_i$ SEK before start refusing you as a customer. Furthermore, a particular store only sells merchandise from a set of categories specific to that store. However, it has products costing any real amount of money from each category.
In order to get-rich-quick, Marika wants to earn as much money per month as possible. How much can she earn if she plans her purchases optimally?
The input consists of:
Output the maximum amount of money Marika can earn per month if purchasing items optimally. Your answer will be considered correct if it has a relative or absolute error of at most $10^{-6}$.
3 10 100 20 50 15 40 5 20 3 1 2 3 20 2 2 3 20 1 2 20 1 3 20 2 1 2
17
Contest > Swedish Coding Cup > LTH Challenge 2017 G번