Let’s say we’ve bought and sold kk GPUs. Then we can write our profit = (s1+s2++sk)(b1+b2++bk)(s_1 + s_2 + … + s_k) - (b_1 + b_2 + … + b_k), where bib_i and sis_i are the buying and selling prices in the shops respectively. So, the buying prices of the GPUs are creating negative impacts on our profit. Now, among the kk GPUs, if a GPU’s buying price is greater than any of the selling price, it will create an overall negative impact and thus only reduce our profit. So, by avoiding this situation, we can gain max profit.

To solve the problem, we will first sort the buying prices in ascending order and sort the selling prices in descending order. We will only buy GPU from the ithi^{th} shop if imi\leq m and the buying price is less than the ithi^{th} selling price. This will ensure we won’t buy any GPU from a shop that will create the above scenario.

Author’s Solution:
C++: https://ideone.com/4u9jfU
Python: https://ideone.com/TOu6XE

Statistics

87% Solution Ratio
Siddik_53rdEarliest, Nov '21
Lumos.603148Fastest, 0.1s
Asif_AlimLightest, 918 kB
silenced.VOICEShortest, 297B
Toph uses cookies. By continuing you agree to our Cookie Policy.