別解です．考察が少ない代わりに，やや高度なテクニックを利用する解法です．

次のような動的計画法 (DP) を考えます．

• \(\mathrm{dp}[i][j] \coloneqq\) \(i\) 種類目までの品物から，重みの総和が \(j\) となるように選んだときの，うれしさの最大値

遷移は次のようになります．

\[ \mathrm{dp}[i][j] \leftarrow \max\{\mathrm{dp}[i-1][j-kw_i] + k v_i - k^2 \mid k=0,\dots,\lfloor j/w_i \rfloor\} \quad (j=0,\dots,W) \]

これを愚直に実装すると，全体の時間計算量は \(O(W^3)\) となり，間に合いません．

この遷移を，convex hull trick を応用することで高速化します．Convex hull trick は本来，いくつかの一次関数の最大値を求めるアルゴリズムですが，関数が互いにたかだか \(1\) 回しか交わらないという性質を持てば，一次関数でないクラスの関数についても同様のアルゴリズムで最大値クエリを処理することができます．今回の遷移では，最高次の係数が等しいいくつかの二次関数の最大値を求められれば良く，そのような関数は互いにたかだか \(1\) 回しか交わらないので，convex hull trick を適用することができます．

今回の DP に convex hull trick を適用する方法を述べます．いま，\(\mathrm{dp}[i][j]\) を計算したいとします．\(j=w_i q + r \, (0 \leq r \leq w_i - 1)\) とし，二次関数の集合 \(S_r\) を次のように定義します．

\[ S_r = \{ f_p(x) \coloneqq \mathrm{dp}[i-1][w_i p + r] + (x - p) v_i - (x - p)^2 \mid p = 0, \dots, q \} \]

すると，\(\mathrm{dp}[i][j] = \max \{ f_p(q) \mid f_p \in S_r \}\) と表すことができます．よって，\(S_0,\dots,S_{w_i-1}\) をそれぞれ convex hull trick を用いて管理することによって，集合への追加と最大値の取得をならし \(O(1)\) 時間で行うことができます．これにより，全体の時間計算量は \(O(NW)\) となります．

また，一次関数の最大値を求めるデータ構造である Li-Chao tree も同様に，互いにたかだか \(1\) 回しか交わらない関数の集合を扱うことができます．Li-Chao tree を利用すれば， \(O(NW \log W)\) 時間のアルゴリズムが得られます．

実装例 (C++)