Shiori Miyagi and Maximum Array Score

Set

$$a_i=i+c_i.$$

Because $a_i<a_{i+1}$, we get

$$i+c_i<i+1+c_{i+1},$$

which is exactly

$$c_i\le c_{i+1}.$$

Also $a_n\le m$, so every offset is in

$$0\le c_i\le m-n.$$

Let

$$R=m-n.$$

So instead of choosing a strictly increasing array, we choose a nondecreasing offset sequence.

Now look at one score:

$$v(i,a_i)=v(i,i+c_i).$$

This score is positive only if

$$i\mid i+c_i.$$

Since $i\mid i$, this is equivalent to

$$i\mid c_i.$$

So row $i$ has useful offsets only at

$$0,i,2i,3i,\ldots\le R.$$

All other offsets give score $0$. They can fill space between useful choices, but they never need to be explicitly chosen.

Points and chains

For every useful choice, create a point

$$(i,c)$$

with weight

$$w(i,c)=v(i,i+c).$$

If we choose several positive-scoring positions, they are compatible exactly when their indices increase and their offsets do not decrease:

$$i_1<i_2<\cdots,$$ $$c_1\le c_2\le\cdots.$$

Skipped indices are harmless: just assign them any offsets between their neighbors. That gives a valid nondecreasing offset sequence.

So the whole problem is now:

Find a maximum-weight chain of points ordered by increasing $i$ and nondecreasing $c$.

That’s weighted LIS in 2D. No need to wrestle the original array directly like it owes you lunch money.

DP with Fenwick tree

Process indices $i=2,3,\ldots,n$.

For a point $(i,c)$,

$$dp(i,c)=w(i,c)+\max dp(j,c')$$

over all previous rows $j<i$ and offsets $c'\le c$.

We need prefix maximum queries over $c$, so use a Fenwick tree storing max DP values.

For each row $i$:

1. Enumerate $c=0,i,2i,\ldots\le R$.
2. Compute $w(i,c)=v(i,i+c)$ by repeated division.
3. Query the Fenwick prefix maximum up to $c$.
4. Save the transition.
5. After finishing the row, update the Fenwick tree with all saved transitions.

That last step is not optional. If you update immediately, row $i$ can use another point from row $i$ as its predecessor, which means choosing two values for the same $a_i$. That’s illegal, and the judge will absolutely not vibe with it.

Why this is exact

Any valid array produces a nondecreasing offset sequence. Every position with positive score gives one point $(i,c_i)$, and those points form a valid chain. So no array can beat the best chain.

Conversely, any valid chain can be expanded into a full nondecreasing offset sequence by filling skipped indices with offsets between their neighboring chosen offsets. The chosen points contribute exactly their weights, and skipped positions may only add more score. So the best chain is attainable.

Complexity

Row $i$ contributes

$$\left\lfloor\frac{R}{i}\right\rfloor+1$$

points. Therefore the total number of points is

$$\sum_{i=2}^n \left(\left\lfloor\frac{R}{i}\right\rfloor+1\right) =O(n+R\log n).$$

Each point does one Fenwick query and one update, so the total complexity is

$$O((n+R\log n)\log R),$$

with $O(R)$ memory. Since the sum of $m$ over tests is at most $2\cdot10^5$, this is comfortably fast.