Crop Harvest

Sort the seeds by increasing coordinate. Suppose the seed at sorted position $j$ was originally seed $p_j$. Thus, $p_j$ is also the only day on which that seed can be harvested.

Consider only the selected seeds, in coordinate order. Their day indices must strictly decrease and then strictly increase, with at most one turning point.

Let the selected seed harvested earliest be the pivot. For selected seeds to the left of the pivot, the day indices must strictly decrease as coordinates increase. Otherwise, when moving to a farther-left seed that must be harvested earlier, Dadas would cross another selected seed that is still unharvested.

For the same reason, the day indices of selected seeds to the right of the pivot must strictly increase as coordinates increase.

Conversely, every selected set whose day indices strictly decrease and then strictly increase can be harvested. Start at the pivot. In chronological order, each next selected seed lies immediately outside the already harvested range on either the left or the right, so the path never crosses another selected seed that is still unharvested.

Therefore, the problem becomes a maximum-weight valley-shaped bitonic subsequence problem on

$$p_1,p_2,\cdots,p_N,$$

where the weight of position $j$ is $w_{p_j}$.

Let $L_j$ be the maximum total value of a strictly decreasing subsequence ending at position $j$. Then

$$L_j=w_{p_j}+\max_{k<j,\ p_k>p_j}L_k.$$

Let $R_j$ be the maximum total value of a strictly increasing subsequence starting at position $j$. Then

$$R_j=w_{p_j}+\max_{k>j,\ p_k>p_j}R_k.$$

Both transitions need the maximum DP value among day indices greater than $p_j$. Since the day indices are exactly the distinct integers from $1$ to $N$, a segment tree indexed by day supports the required range maximum queries.

Compute $L_j$ from left to right. Query the maximum on $(p_j,N]$, add $w_{p_j}$, and update position .

Compute $R_j$ from right to left in the same way.

If position $j$ is the pivot, the best value is

$$L_j+R_j-w_{p_j},$$

because the pivot weight was counted twice.

The maximum of this expression over all $j$ is the answer. Sorting and segment tree operations give $O(N\log N)$ time and $O(N)$ memory.

All weights are positive, so the answer is at most the sum of all weights. Hence,

$$\text{answer}\leq N\cdot10^9\leq2\cdot10^{14},$$

which always fits in a signed 64-bit integer.

Solution written by GPT5.6