CF1515I Phoenix and Diamonds

Phoenix wonders what it is like to rob diamonds from a jewelry store! There are $ n $ types of diamonds. The $ i $ -th type has weight $ w_i $ and value $ v_i $ . The store initially has $ a_i $ diamonds of the $ i $ -th type. Each day, for $ q $ days, one of the following will happen: 1. A new shipment of $ k_i $ diamonds of type $ d_i $ arrive. 2. The store sells $ k_i $ diamonds of type $ d_i $ . 3. Phoenix wonders what will happen if he robs the store using a bag that can fit diamonds with total weight not exceeding $ c_i $ . If he greedily takes diamonds of the largest value that fit, how much value would be taken? If there are multiple diamonds with the largest value, he will take the one with minimum weight. If, of the diamonds with the largest value, there are multiple with the same minimum weight, he will take any of them. Of course, since Phoenix is a law-abiding citizen, this is all a thought experiment and he never actually robs any diamonds from the store. This means that queries of type $ 3 $ do not affect the diamonds in the store.

N/A

N/A

For the first query where $ t=3 $ , Phoenix can fit $ 2 $ diamonds of type $ 1 $ , with total weight $ 6 $ and value $ 8 $ . For the second query where $ t=3 $ , Phoenix will first fit in $ 3 $ diamonds of type $ 3 $ , then one diamond of type $ 1 $ for a total weight of $ 9 $ and a value of $ 16 $ . Note that diamonds of type $ 3 $ are prioritized over type $ 1 $ because type $ 3 $ has equal value but less weight. For the final query where $ t=3 $ , Phoenix can fit every diamond for a total value of $ 13 $ .