Hints: https://atcoder.jp/contests/arc210/editorial/14585

We write \(r=1.01\).

[1] Solution

First, as a trivial solution, we can consider the following:

• Let \(X_i\) be the multiset of all subsequence sums of \(a_1,\ldots,a_i\).
• \(X_{i+1}\) is obtained by \(X_i\cup \{s+a_{i+1}\mid s\in X_i\}\).

This gives a solution with time complexity \(O(N\max |X_i|)\). However, \(|X_i|\) is too large, so let us appropriately discard information unnecessary for computing the answer and reduce the states to be maintained.

The following is easy to see: if \(0\leq s\leq t\leq rs\), then \(0\leq s+a\leq t+a\leq r(s+a)\) for any \(a>0\).

Now, let \(X_i = \{s_1,s_2,\ldots\}\) (in ascending order). If \(s_L\leq s_R\leq r s_L\) holds for \(L\leq R\), replacing all of \(s_{L+1},\ldots,s_{R-1}\) with \(s_L\) does not change the answer. This can be easily proved by induction on the number of remaining operations, for example.

We always reduce the number of distinct elements in \(X_i\) by this method as much as possible, and instead maintain the frequency of each element.

If the distinct elements in \(X_i\) at some point are \(x_1<x_2<\cdots\), then \(r x_i \leq x_{i+2}\) holds, so the number of distinct elements to be maintained is \(O(\log_r (\sum A_i))\).

From the above, this problem can be solved in \(O(N\log_r(\sum A_i))\) time.