人类智慧。
答案显然具有可二分性，考虑如何check。
我们使用调整法，不妨设 \(x_n<y_m\) （反着做同理），一开始我们令 \(x_i=1,y_i=+\infty\)。每次我们期望让 \(x\) 不断变大，\(y\) 不断变小，不断将它们调整到当前的上下界。具体的，每次令 \(x_i=\max \{x_i, \max \lceil {a_{i,j}-k\over y_j} \rceil\}, y_i = \min \{y_i, \min \lfloor {a_{i,j}+k\over x_j} \rfloor \}\)。为了保证单调性，还需令 \(x_i=\max\{x_i,x_{i-1}+1\}\),\(y_i=\min\{y_i,y_{i+1}-1\}\)
显然在任意时刻，都存在合法的 \(x\) 大于等于当前的 \(x\)，最后一定会到一个合法解。如果当前 \(x_n>y_m\) 或 \(y_1 \le 0\) 就直接 break.
考虑它的复杂度，每个 \(x\) 至多会增加到根号值域，由于 \(n,m\) 很小，可以轻松跑过。
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
inline int read() {
register int s = 0, f = 1; register char ch = getchar();
while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
return s * f;
}
typedef long long ll;
const ll inf = 2e9;
ll a[N][N], x[N], y[N];
int n, m;
inline ll abs_(ll a) {
return a < 0 ? -a : a;
}
inline bool chk(ll k) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (x[i] <= 0 || y[j] <= 0 || abs_(x[i] * y[j] - a[i][j]) > k) return 0;
return 1;
}
inline bool check(ll k) {
for (int i = 1; i <= n; ++i) x[i] = 1;
for (int i = 1; i <= m; ++i) y[i] = inf;
y[m + 1] = inf + 1;
while (1) {
for (int i = 1; i <= n; ++i) {
ll r = -1;
for (int j = 1; j <= m; ++j)
r = max(r, (a[i][j] - k + y[j] - 1) / y[j]);
x[i] = max(max(x[i], x[i - 1] + 1), r);
}
for (int i = m; i; --i) {
ll r = inf;
for (int j = 1; j <= n; ++j)
r = min(r, (a[j][i] + k) / x[j]);
y[i] = min(min(y[i], y[i + 1] - 1), r);
} if (chk(k)) return 1;
if (x[n] > y[m] || y[1] <= 0) break;
}
for (int i = 1; i <= n; ++i) x[i] = inf;
for (int i = 1; i <= m; ++i) y[i] = 1;
x[n + 1] = inf + 1;
while (1) {
for (int i = 1; i <= m; ++i) {
ll r = -1;
for (int j = 1; j <= n; ++j)
r = max(r, (a[j][i] - k + x[j] - 1) / x[j]);
y[i] = max(max(y[i], y[i - 1] + 1), r);
}
for (int i = n; i; --i) {
ll r = inf;
for (int j = 1; j <= m; ++j)
r = min(r, (a[i][j] + k) / y[j]);
x[i] = min(min(x[i], x[i + 1] - 1), r);
} if (chk(k)) return 1;
if (y[n] > x[m] || x[1] <= 0) break;
}
return 0;
}
int main() {
n = read(); m = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) a[i][j] = read();
ll l = 0, r = 1e9, mid, res = r;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) r = (res = mid) - 1;
else l = mid + 1;
} check(res);
printf("%lld\n", res);
for (int i = 1; i <= n; ++i) printf("%lld ", x[i]);
puts("");
for (int i = 1; i <= m; ++i) printf("%lld ", y[i]);
return 0;
}