tester解です。

---

[0]定義

整数 \(i,\ x\ (1 \le i \le N^2,\ 1\leq x \le S)\) に対し、 \(A_{j}=x,\ i < j\) を満たす最小の \(j\) を \(\mathrm{front}(i,x)\) と書きます（そのような \(j\) が存在しない場合、\(\mathrm{front}(i,x)=\infty\) とします）。これは \(O(N)\) で前処理を行うことで毎回 \(O(\log N)\) で求めることができます。

長さ \(n\) の整数列 \(X=(X_1,\ X_2,\ \dots,\ X_n)\) に対し、以下が成り立つ最大の \(s\) を \(f(X)\) と書きます。

• 総和が \(s\) であるような任意の正整数列 \(Y\) が \(X\) の部分列となる。

---

[1] 配るdp

\(dp_s\) を \(f((A_1,\ A_2,\ \dots,\ A_i))=s\) を満たす最小の \(i\) とします（総和が \(s\) である正整数列のうち、最終項が \(1\) であるものを考えるとこのような \(i\) は必ず存在することがわかります）。

総和が \(s\) の正整数列のうち、最終項が \(x\) であるものを考えます。これが \((A_1,\ A_2,\ \dots,\ A_i)\) の部分列となるのは \(\mathrm{front}(dp_{s-x},x) \leq i\) のときなので \(\displaystyle dp_s=\max_{1\leq x \leq s} \mathrm{front}(dp_{s-x},x)\) です。

これは \(dp_s=0\ (1\leq s \leq S)\) で初期化し、\(s=0,\ 1,\ \dots,\ S-1\) の順に \(dp_{s+x}\leftarrow \max(dp_{s+x},\ \mathrm{front}(dp_s, x))\) と更新していく「配るdp」により求めることができます。

---

[2] 分割統治法による高速化

上記の配るdpを分割統治法により高速化します。

\(dp_{l},\ dp_{l+1},\ \dots,\ dp_{r}\) について求めることを考えましょう。順番としては \(m=\lfloor \frac{l+r}{2} \rfloor\) として

• \(dp_{l},\ dp_{l+1},\ \dots,\ dp_{m-1}\) を再帰的に求める
• \(dp_{l},\ dp_{l+1},\ \dots,\ dp_{m-1}\) の分の寄与を \(dp_{m},\ dp_{m+1} ,\ \dots,\ dp_r\) に配る
• \(dp_{m},\ dp_{m+1},\ \dots,\ dp_{r}\) を再帰的に求める

とすればよく、\(2\) 番目が高速に処理できればいいです。

まず \(dp_{l},\ dp_{l+1},\ \dots,\ dp_{m-1}\) の分の寄与を \(dp_{m},\ dp_{m+1} ,\ \dots,\ dp_r\) に配る際は \(x=1,\ 2,\ \dots,\ r-l\) だけ考えればいいです。

各 \(x\) についてどのように処理すればいいか考えましょう。\(dp_s\) の \(s\) についての単調性から、 \(\mathrm{front}(dp_{s},x)\) が \(dp_{m-1}\) 未満であるような \(s\) については配る必要がありません。よって \(\mathrm{front}(dp_s,\ x)=\mathrm{front}(dp_{m-1},\ x)\) であるような \(s\) のみを考えればよく、そのような \(s\) は区間になっています。

よって各 \(x\) について \(\mathrm{front}(dp_s,\ x)=\mathrm{front}(dp_{m-1},\ x)\) を満たす最小の \(s\ (l \leq s \leq m-1)\) を求め（ \(m_x\) とします）、\(m_x \leq s \leq m-1\) に対し \(dp_{s+x}\leftarrow \max(dp_{s+x},\ \mathrm{front}(dp_{m-1},\ x))\) で更新すればいいです。

これは区間chmax一点取得のセグメント木を用いることで各 \(x\) について \(O(\log S)\) でできます。

以上を実装することでこの問題は \(O(N+S\log{S}(\log S + \log N))\) で求めることができます。