Problem 4: Financial Planning

https://open.kattis.com/problems/financialplanning

Given an integer $d$ representing the number of days elapsed, we can determine the total profit following the optimal investment strategy. This involves only choosing investments that bring in a net profit after $d$ days. We can do this by thinking of each investment option as a linear function of the form $P(d) = p_id - c_i$, where $P(d)$ is the net profit (or loss).

We want to find the earliest day $d$ so that the profit following the optimal investment strategy is at least $M$.

We can compute the profit following the optimal investment strategy for $d = 1$ onwards and take the first $d$ whose profit is at least $M$. However this is too slow.

• If $d$ is not a day where the profit following the optimal investment strategy is at least $M$, then all days before $d$ do not have profits reaching$M$.

• However, if $d$ is a day where the profit following the optimal investment strategy is at least $M$, then all days after $d$ can't be the earliest day with profits of at least $M$.

Therefore, we can find the earliest day $d$using binary search.

This solution requires arithmetic with potentially very large numbers, so use long long (or even __int128) whenever possible.