Tester 解の方が簡潔で分かりやすいので先にそちらを読むことをお勧めします。

\(S_i=X_{i+1}-X_i\) とします。このとき、 \(S\) に含まれる値は高々 \(2\) 種類である必要があり、さらに \(2\) 種類の場合はそれらの値は隣り合う必要があります。また、 \(X_i \leftarrow X_i - i \times \min S\) とすることで問題を \(\lbrace S\rbrace = \lbrace 0\rbrace, \lbrace 0,1\rbrace\) のいずれかの場合に帰着させることができます。切片も同様に考えることで、 \(X_0=0\) に帰着させることができます。

(1) \(\lbrace S\rbrace = \lbrace 0\rbrace\) のとき

\(M\) がある値 \(M_0\) 以下であるような良い組の個数は一次式の和として表すことができます。したがって、二分探索を用いることで辞書順で \(K\) 番目に小さい良い組を求めることができます。

(2) \(\lbrace S\rbrace = \lbrace 0,1\rbrace\) のとき

\(T=\lbrace i | X_i+1=X_{i+1}\rbrace\) とします。

このとき、\(i \in T\) に対し線分 \(\displaystyle y=\frac{Ax+B}M\) は \((i,X_i),(i+1,X_{i+1})\) を端点とする（ただし \((i+1,X_{i+1})\) を含み \((i,X_i)\) を含まない）線分を通る必要があります。したがって、 \(x\) 軸と \(y\) 軸を反転させた問題を考えることで長さ \(T\) の同じタイプの問題に帰着させることができます。

しかし、このまま素朴に実装しようとすると両端の情報を落としてしまう場合があります。例えば以下のようなケースを考えます。

5 1
0 0 1 2 2

この場合 \(T=\lbrace 1,2\rbrace\) ですが、小さい問題に帰着させた場合 \(X_0\) と \(X_4\) の情報が消えてしまいます。

このような状況を別で考えることにすると、再帰的に考えるケースの終着点は以下の \(5\) 通りとなることが分かります。

• 0 0 0 型：\(|T|=0\) となる場合、つまり \(X\) が全て \(0\) となる場合。
• 0 0 1 1 1 型：\(X\) がちょうど \(2\) 通りの値を取る場合。
• 0 0 1 1 2 2 型：\(T\) が等差数列となり、さらに \(X_0\) と \(X_{N-1}\) の値が両方重要な場合。
• 0 1 1 2 2 型：\(T\) が等差数列となり、さらに \(X_{N-1}\) の値が重要な場合。
• 0 0 1 1 2 型：\(T\) が等差数列となり、さらに \(X_0\) の値が重要な場合。

これら \(5\) 通りの場合が再帰の終着点となります。また、この条件を満たす直線 \(\displaystyle y=\frac{ax+b}m\) が得られた場合、求める答えは再帰の過程で得られる \(c_1,c_2,c_3,c_4,c_5,c_6\) を用いて \((M,A,B)=(c_1m+c_2a,c_3m+c_4a,c_5a+c_6m+b)\) と表されます。したがって、各型に対し条件を満たす中で \((c_1m+c_2a,c_3m+c_4a,b)\) の値が \(K\) 番目に小さくなるような直線を求めることができればよく、これは floor sum を用いることで高速に計算することができます。

以上を適切に実装することでこの問題に正答することができます。