Hints: Merchant Takahashi

Hint 1 ↕

Define dp[i] to be the maximum profit that you can get with the currently processed markets such that you are currently stand at town i. When a new market at town t is introduced, how are the DP values refreshed?

Answer to Hint 1 ↕

For each town i, you can try to move to town t and update the DP value of town t if it gets improved. The time complexity of this solution is O(n^2).

Code

Hint 2 ↕

While processing a town t, divide other towns into 2 groups, one on the left hand side, and one of the right hand side of town t. Now, notice that the contribution of each town depends on its index. So let’s isolate the contribution into 2 parts, one that comes from the current town with index i, and the other that comes from town t.

Define

ldp[i] = dp[i] + c*t
rdp[i] = dp[i] - c*t

Using ldp and rdp, how do you refresh the DP values of town t?

Answer to Hint 2 ↕

dp[t] = max(dp[t], pref_max(ldp[0...t - 1]) + p - c*t)
dp[t] = max(dp[t], suff_max(rdp...[t...] + p + c*t))

Code

Hint 2 ↕

While processing a town t, divide other towns into 2 groups, one on the left hand side, and one of the right hand side of town t. Now, notice that the contribution of each town depends on its index. So let’s isolate the contribution into 2 parts, one that comes from the current town with index i, and the other that comes from town t.

Define

ldp[i] = dp[i] + c*t
rdp[i] = dp[i] - c*t

Using ldp and rdp, how do you refresh the DP values of town t?

Hint 3 ↕

We only need prefix maximas and suffix maximas from ldp and rdp. So use a segtree to efficiently query these values.

Code