Bonus の解説を書きます。( おそらく合っていると思いますが、間違っていたらすいません。 ) $S_i$ の最大値を $S_{max}$ とします。

Bonus 1

前準備として $S=i$ となりうるかを $1 \leq i \leq 10^3$ について求めておけば問題には $O(1)$ で答えられます。
公式解説と同様に考えることで $a,b \leq 10^3$ の範囲で $S$ の値を全て求めればよいので、前準備は $O({S_{max}}^2)$ で行えます。よってこの問題は $O(N+{S_{max}}^2)$ で解けました。

Bonus 2

同様に前準備することを考えます。 $a$ を決めた時に調べる必要のある $b$ の値を考えます。 $(4a+3)b + 3a = 4ab+3a+3b \leq S_{max}$ より $b \leq \frac{S_{max}-3a}{4a+3}$ であり、個数の上界は $\frac{S_{max}}{a}$ 個です。
$1 \leq a \leq S_{max}$ より $S$ を求める必要のある $\left(a ,b \right)$ の個数の上界は $S_{max} \left( \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{S_{max}} \right)$ です。直感的にこれは $O( {S_{max}}^2)$ に思えますが積分を用いることで、これは $O(S_{max} \log S_{max})$ になることが示せます。 ( 調和級数 で調べると参考になるでしょう。 )
結論として前準備は $O(S_{max} \log S_{max})$ でできるので、この問題は $O(N+S_{max} \log S_{max})$ で解けました。

Bonus 3

\(a \leq b\) としても構いません。ここで、 \(4a^2 \leq 4ab < S_i\) より \(a \leq \sqrt{S_i}\) です。
\(a\) を決めた時、 \(4ab+3a+3b=S_i\) を満たす \(b\) が存在するかは一次方程式を解く要領で \(O(1)\) で判定できます。
よって、各問題につき \(O(\sqrt{S_i})\) で解けるので、この問題は \(O(N \sqrt{S_{max}})\) で解けました。