\(M = 10^9\) とします。明らかに \(D_{min} \leq M\) です。

\(D\) について二分探索を行い、ペナルティが \(D\) 以下の解を探索します。まず、\(x_i\) を可能な最小値、\(y_i\) をいかなる解における値よりも大きな値に初期化します。例えば \(x_i = i, y_j = D + M + j\) です。

\(x_i y_j\) の下界 \(L_{i, j} = \max(1, a_{i, j} - D)\) と上界 \(R_{i, j} = a_{i, j} + D\) を定義します。これから、必要が生じるたびに \(x_i\) を増やし、\(y_j\) を減らします。すなわち、以下の通りです。

• \(x_i y_j > R_{i, j}\) なら、\(y_j = \lfloor R_{i, j} / x_i \rfloor\) とできる。
• \(x_i y_j < L_{i, j}\) なら、\(x_i = \lceil L_{i, j} / y_j \rceil\) とできる。
• \(x_i \geq x_{i + 1}\) なら、\(x_{i + 1} = x_i + 1\) とする。
• \(y_j \geq y_{j + 1}\) なら、\(y_j = y_{j + 1} - 1\) とする。

あらゆる時点において、\(x_i\) が、ペナルティ \(D\) 以下の任意の解に対する無条件の下界となっていることに注意します。同様に、\(y_i\) は無条件の上界となっています。従って、解が存在すれば、このプロセスで必ず発見されます。

ここで、解において \(x_n \leq y_m\) であるという仮定を追加します（反対の場合はこれと対称的になります）。\(x_n > y_m\) となるか、いずれかの \(j\) に対して \(y_j \leq 0\) となったらプロセスを打ち切ることにします。\(x_n y_m \leq D + M\) であるため、\(x_n \leq \sqrt{D + M}\) です。従って、プロセス全体で \(x_i\) が増加するのは \(n \sqrt{D + M}\) 回以下、\(y_i\) が減少するのは \(n m \sqrt{D + M}\) 回以下であり、行われる操作は合計で \(n^2m \sqrt{D + M}\) 回以下となります（\(y_j\) が減少するたびに \(O(n)\) 個の条件を確認する必要があることに注意）。

合計計算量は \(O(nm(n + m) \sqrt{M} \log{M})\) です。また、上の解法には、二分探索をしない計算量 \(O(nm(n + m) \sqrt{M})\) の亜種もあります。