次の (性質) に注目します： \(x < x'\) なら、 \(ax + b < ax' + b\) である。

列挙

最適の数列を \((q_1, q_2, \cdots, q_K)\) と仮定します。 \(p_K, p_{K-1}, \cdots, p_1\) の順に \(p_i\) を決めていくことを考えます。

\(p_K\) を決める

• \(A_i + B_i\) の値が大きい順に \(K\) 個の関数を選びます。
  • その中の少なくとも \(1\) つは \(\{q_1, q_2, \cdots, q_{K-1}\}\) に含まれません。
  • ここで、(性質) によって、その集合の中に \(q_K\) があると仮定して構いません。
• よって、これら \(K\) 個から関数を \(1\) つ選び 、 \(p_K\) とします（ \(p_K\) はすべて試します）

\(p_{K-1}\) を決める

\(p_K\) をすでに決めたとします。ここで、 \(p_K = q_K\) であったと仮定します。

• \(p_K\) 以外の \(i\) のうち、 \(A_i + B_i\) の値が大きい順に \(K-1\) 個の関数を選びます。
  • その中の少なくとも \(1\) つは \(\{q_1, q_2, \cdots, q_{K-2}\}\) に含まれません。
  • ここで、(性質) によって、その集合の中に \(q_{K-1}\) があると仮定して構いません。
• よって、これら \(K-1\) 個から関数を \(1\) つ選び 、 \(p_{K-1}\) とします（ \(p_{K-1}\) もすべて試します）

同様に続けていく

\(p_K, p_{K-1}\) をすでに決めたとします。

• \(p_{K}, p_{K-1}\) 以外の \(i\) のうち、\(x = A_{p_{K-1}} (A_{p_K} + B_{p_K}) + B_{p_{K-1}}\) として、 \(A_i x + B_i\) が大きい順から \(K-2\) 個に関数を選びます。
• 同様に \(p_{K-2}\) を選びます。

まとめ

このようにして、 \((p_1, p_2, \cdots, p_K)\) を列挙すると、その中に必ず最適な \((q_1, q_2, \cdots, q_K)\) があることが保証され、最適解が求まります。この方法では、数列 \((p_1, p_2, \cdots, p_K)\) は \(K!\) 通り列挙することになります。

工夫

各 \(x\) に対し、 \(A_i x + B_i\) が大きい順から \(K\) 個を求めればよいです。しかし、ここで時間計算量の工夫が必要です。制約の \(1 \le B_i \le 50\) に注目すると、 \(x \ge 50\) のとき、 任意の \(t\) について

\[tx + 50 < (t+1)x + 1\]

が成り立ちます。よって、上位 \(K\) 個を求める必要がある \(x\) は \(x=1,2,\cdots, 50\) のみです。各 \(x\) について時間計算量 \(O(NK)\) で \(A_i x + B_i\) の上位 \(K\) 個を求めることができます。

計算量

最終的な計算量は以下のようになります。

• \(x=1,2,\cdots, 50\) に対して、\(A_i x + B_i\) の値の上位 \(K\) 個を求めるときに \(O(NK \max B_i)\) 時間
• 数列 \(p\) の列挙に \(O(K \times K!)\) 時間

かかります。以上より、時間計算量 \(O(NK \max B_i + K \times K!)\) 、空間計算量 \(O(NK)\) となり、この計算量なら実行時間制限に間に合います。

shobonvipの実装 (C++, 260ms)