# Hints: Merchant Takahashi

`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?
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)`

.

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`

?

```
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))
```

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`

?

We only need prefix maximas and suffix maximas from `ldp`

and `rdp`

. So use a segtree to efficiently query these values.