Codeforces 1150A. Stock Arbitraging Codeforces Round #556 (Div. 2)

Problem link

The main observation is that we always want to buy shares as cheaply as possible, and sell them as expensively as possible. Therefore, we should pick the lowest price at which we can buy shares smin=min(s1,s2,…, Sn), and the highest price at which we can sell the shares bmax=max(b1,b2,…, Bm). Now, we have two cases:

If smin<bmax, it's optimal to buy as many shares and possible in the morning and sell them all in the evening. We can buy as many as ⌊r / Smin⌋ shares and gain Bmax−Smin bourles profit on each of them. Therefore, the final balance is r + ⌊r / Smin⌋(Bmax−Smin).
If Smin≥Bmax, we're not gaining any profit on the shares and therefore we shouldn't care about trading stocks at all. The final balance is then r.
The solution can be therefore implemented in O(n+m) time. However, the constraints even allowed brute-forcing the seller, the buyer and the amount of stock we're buying in O(nmr) time.


A solution in c++