難易度 \(l\) において \(T\) 秒後で \(P_i\geq K\) であるすべての \(i\) についての \(h_i\) の総和としてありうる最小値を \(f(K,l)\) と置きます。

このとき、\(T\) 秒後の評価値の最小値は \(\displaystyle\sum_{k=1}^{P_{\max}}f(k,l)\) となります。

ここで、\(P_i\) の値は高々 \(N\) 種類なので、 \(f(k,l)\) は高々 \(N\) 種類であることがわかります。

難易度 \(l\) の値を動かしたときの \(f(K,l)\) について考えます。

\(P_i\geq K\) なる \(i\) を \(i_1,i_2,\dots,i_m\) \(\left(S_{i_1}<S_{i_2}<\dots<S_{i_m}\right)\) とすると、

\(f(K,l)=\max(S_{i_1}+(H_{i_1}+H_{i_2}+\dots+H_{i_m})\times l-T,S_{i_2}+(H_{i_2}+\dots+H_{i_m})\times l-T,\dots,S_{i_m}+H_{i_m}\times l-T,0)\)

となり、つまり \(m\) 個（つまり高々 \(N\) 個）の直線の最大値のような表示が得られます。

ここで、\(f(K,l)\) は高々 \(N\) 個の線分でできた関数と見ます。

このとき \(f(1,l),f(2,l),\dots,f(P_{\max},l)\) でできる \(\displaystyle\sum_{k=1}^{P_{\max}}f(k,l)\) は 高々 \(N\) 個の線分からなる高々 \(N\) 個の関数の和となり（\(f(k,l)\) の種類が \(P_i\) の種類から高々 \(N\) 個であるので）、結局高々 \(N^2\) 個の線分でできた関数となります。

これを前計算 ( \(O(N^2 \log N)\) ）することによって、

\(l\) を固定したときの \(\displaystyle\sum_{k=1}^{P_{\max}}f(k,l)\) の値を \(O(1)\) で求められるようになり、愚直に \(l=0,1,\dots,L\) についてこの値を \(O(L)\) で計算することでクエリに \(O(Q+L)\) で答えることができます。

全体の計算量は \(O(N^2\log N+Q+L)\) です。

実装例(C++ 1824ms)