まずは問題文を整理してみます。高橋くんのテストの点数を$a_i$とおくと、次の問題になります。
この問題を解こうとするときに困る点は、決めなければならない値が、$a_i$と$c_i$の2つあることです。どちらかをなくすことができれば、$\sum a_i$の最小値は貪欲や二分探索を使って求められそうです。
ここで、3つ目の条件式を変形してみます。すると、次の式が得られます。
$a_i$の値が決まっているとすると、$a_i - b_i \lt 0$の場合は$c_i$をできるだけ小さくすればいいこと、$a_i - b_i \ge 0$の場合は$c_i$をできるだけ大きくすればいいことがわかります。このように$c_i$を選ぶことで、上の条件を満たしやすくなります。そしてこの問題では、「できるだけ小さくする」は$l_i$にすること、「できるだけ大きくする」は$u_i$にすることです。ということで、$D_i(a_i) = (a_i - b_i) \times c_i$とおくと、$D_i(a_i)$は次の式になります。
\[D_i(a_i) = \begin{cases} l_i \times (a_i - b_i) & (a_i - b_i \lt 0) \\ u_i \times (a_i - b_i) & (a_i - b_i \ge 0) \\ \end{cases}\]$D_i(a_i)$を使って問題を書き直すと、次のようになります。
$c_i$をなくすことができました。決めなければならない値が$a_i$だけになりました。
$a_i$が非負整数であることを加味すると、更に次の問題に言い換えられます。
「長さ$X$の数列が$N$個」を図で表すと、次のようになります。
\begin{array}{llllllllllllll}
l_1 & l_1 & l_1 & \ldots & l_1 & u_1 & \ldots & u_1 & u_1 & u_1 & u_1 & u_1 & u_1
l_2 & l_2 & l_2 & l_2 & l_2 & \ldots & l_2 & u_2 & \ldots & u_2 & u_2 & u_2 & u_2
l_3 & \ldots & l_3 & u_3 & u_3 & u_3 & u_3 & \ldots & u_3 & u_3 & u_3 & u_3 & u_3
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots
l_N & l_N & l_N & l_N & \ldots & l_N & u_N & \ldots & u_N & u_N & u_N & u_N & u_N
\end{array}
この問題の解き方ですが、二分探索で解くことを考えます。すなわち、$\sum a_i$の値（これを$k$とおきます）を決めて、そのときに$\sum l_ib_i$以上にすることができるかどうかという問題を考えます。
実はこのとき、$1$個以上$X - 1$個以下を選ぶ数列の個数は高々ひとつです。つまり、それ以外の数列については、$0$個か$X$個を選ぶことになります。これを証明します。
もし$1$個以上$X - 1$個以下を選ぶ数列が2つあるとします。この数列を$x_i, y_i(0 \le i \le X)$とします。そして、各数列で選ぶ個数を$z, w$とします。
$x_z \gt y_w$のとき、$z+w$を変えずに$z$を限りなく大きくし、$w$を限りなく小さくすることで、選ぶ個数を変えることなく総和を大きくできます（数列は広義単調増加、という性質からわかります）。限りなく進んだ結果、$z,w$のどちらか（もしくはどちらも）が、$0$か$X$になります。これで、$1$以上$X-1$以下を選ぶ数列の個数が高々ひとつになりました。
$x_z \lt y_w$のときも同じように考えることで、$1$以上$X-1$以下を選ぶ数列の個数を1以下にすることができます。
$x_z = y_w$のときは、どちらを大きくしても構いません。これは、数列に単調性があることからわかります。どちらを大きくしても、総和は必ず元の総和以上になります。そして最終的に、$1$以上$X-1$以下を選ぶ数列の個数を1以下にすることができます。
よって、$1$個以上$X - 1$個以下を選ぶ数列の個数は高々ひとつになることがわかりました。
$k$は決まっているため、$X$個選ぶ数列の個数$q$と、$1$個以上$X-1$個以下選ぶ数列の要素の個数$r$は簡単に求められます。このときに、どの数列を$1$個以上$X-1$個以下にするかは全探索することにします。この数列を取り除いた数列から$q$個の数列を選ぶ必要がありますが、これは前計算しておくことで$O(1)$で求めることが可能です。そして、$r$個選んだときの和も簡単な計算で求めることができるため、全体で$O(N)$となります。二分探索の計算量も合わせると、全体の計算量は$O(N (\log NX))$となり、この問題を解くことができました。
ソースコードはこちらです。けっこう複雑になってしまいました…。
証明をしてみました。証明するのは大変でした…。というかもしかすると、きちんと証明できていないかもしれません。もし何かお気付きのことがありましたら、Twitterでご指摘いただけると嬉しいです。
この問題からは、2つのことを学びました。
制約が$N \le 10^5$の問題は、一見複雑に見えても、ひとつずつ紐解いていくことでよく見る形の問題に帰着できることが多い気がします。まずはこういった問題を安定して解けるようになりたいです。