Yura and Deadlines

The condition looks global because it mentions every pair of chosen assignments. Fortunately, the global part collapses into a local one.

1. Only consecutive chosen indices matter

Suppose the chosen indices are $p_1<p_2<\dots<p_k.$

Assume every consecutive pair is valid. Consider any nonconsecutive pair $p_r<p_s$.

Because $p_{r+1}$ lies between them, $p_s-p_r>p_{r+1}-p_r>a_{p_r}.$

Similarly, using the last gap before $p_s$, $p_s-p_r>p_s-p_{s-1}>a_{p_s}.$

Therefore $p_s-p_r>\max(a_{p_r},a_{p_s}),$ so that pair is valid too. Thus it is enough to ensure compatibility between consecutive selected assignments.

That turns the problem into finding a maximum-weight path through indices from left to right.

2. The DP transition

Define $dp[j]$ as the maximum total weight of a valid selection whose rightmost chosen assignment is $j$.

If $i<j$ is the previous chosen index, compatibility requires $j-i>\max(a_i,a_j).$

This is equivalent to satisfying both $j-i>a_i$ and $j-i>a_j.$

Rearranging them gives $i+a_i<j$ and $i<j-a_j.$

Since all values are integers, the second inequality becomes $i\le j-a_j-1.$

Hence $dp[j]=a_j+\max_{\substack{i+a_i<j\\i\le j-a_j-1}}dp[i].$

If no such $i$ exists, the best selection ending at $j$ contains only $j$, so $dp[j]=a_j$.

A quadratic implementation would inspect every earlier $i$. That is obviously dead on arrival for $n=2\cdot10^5$, so we need to separate the two restrictions.

3. Activating usable previous indices

Sweep $j$ from left to right.

The restriction $i+a_i<j$ becomes permanently true starting at $j=i+a_i+1.$

Call $i$ active from that time onward. When computing $dp[i]$, we schedule index $i$ to be activated at time $i+a_i+1$. If this time is larger than $n$, it can never be used by any later assignment and does not need to be scheduled.

At the start of step $j$, every active index already satisfies the first transition restriction. Among those indices, we still need the maximum $dp[i]$ with $i\le j-a_j-1.$

That is a prefix-maximum query by index.

4. Fenwick tree for prefix maximums

A Fenwick tree is usually introduced for sums, but its update/query structure works just as well for monotone maximums:

• update(i, value) records that position $i$ has value value;
• query(r) returns the maximum value among positions $1$ through $r$.

We never remove active indices, so maximum updates are perfect here.

For each position $j$:

1. Insert every index whose activation time is exactly $j$ into the Fenwick tree using its already-computed $dp$ value.
2. Compute $r=j-a_j-1.$
3. Query the maximum active $dp[i]$ over $i\le r$.
4. Set $dp[j]=a_j+\operatorname{query}(r).$
5. Schedule $j$ for activation at $j+a_j+1$, if that time is at most $n$.

A query with $r\le0$ simply returns $0$, representing starting a new selection at $j$.

5. Why the algorithm is correct

We prove by induction over $j$ that $dp[j]$ is the best score of any valid selection ending at $j$.

For a selection containing only $j$, the score is $a_j$, which the transition can always produce because the empty-prefix value is $0$.

Now consider a valid selection ending at $j$ with some previous chosen index $i$. Since $i$ and $j$ are consecutive in that selection, they must satisfy $i+a_i<j$ and $i\le j-a_j-1$. Therefore $i$ is active when step $j$ begins and lies inside the queried Fenwick prefix. By the induction hypothesis, $dp[i]$ is the best score ending at $i$, so the algorithm considers a score at least as large as this selection's prefix plus $a_j$.

Conversely, every index returned by the query is active, hence satisfies $i+a_i<j$, and is inside the queried prefix, hence satisfies $i\le j-a_j-1$. Thus $i$ and $j$ are compatible. Appending $j$ to an optimal selection ending at $i$ creates a valid selection, because checking consecutive chosen indices is sufficient.

So the transition considers exactly all valid possibilities, and $dp[j]$ is correct. The final answer is $\max_{1\le j\le n}dp[j],$ with $0$ also implicitly allowed for the empty subset.

Complexity

Each index is inserted into the Fenwick tree at most once and causes one prefix query.

• Time: $O(n\log n)$ per test case
• Memory: $O(n)$

Across all test cases, the total $n$ is at most $2\cdot10^5$.