Codeforces Round\# 531 (Div. 3) F. Elongated Matrix (상 압 + 검색)

F. Elongated Matrix
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given a matrix aa, consisting of nn rows and mm columns. Each cell contains an integer in it.
You can change the order of rows arbitrarily (including leaving the initial order), but you can't change the order of cells in a row. After you pick some order of rows, you traverse the whole matrix the following way: firstly visit all cells of the first column from the top row to the bottom one, then the same for the second column and so on. During the traversal you write down the sequence of the numbers on the cells in the same order you visited them. Let that sequence be s1,s2,…,snms1,s2,…,snm.
The traversal is kk-acceptable if for all ii (1≤i≤nm−11≤i≤nm−1) |si−si+1|≥k|si−si+1|≥k.
Find the maximum integer kk such that there exists some order of rows of matrix aa that it produces a kk-acceptable traversal.
Input
The first line contains two integers nn and mm (1≤n≤161≤n≤16, 1≤m≤1041≤m≤104, 2≤nm2≤nm) — the number of rows and the number of columns, respectively.
Each of the next nn lines contains mm integers (1≤ai,j≤1091≤ai,j≤109) — the description of the matrix.
Output
Print a single integer kk — the maximum number such that there exists some order of rows of matrix aa that it produces an kk-acceptable traversal.
Examples
input
Copy

4 2
9 9
10 8
5 3
4 3

output
Copy

5

input
Copy

2 4
1 2 3 4
10 3 7 3

output
Copy

0

input
Copy

6 1
3
6
2
5
1
4

output
Copy

3

Note
In the first example you can rearrange rows as following to get the 55-acceptable traversal:

5 3
10 8
4 3
9 9

Then the sequence ss will be [5,10,4,9,3,8,3,9][5,10,4,9,3,8,3,9]. Each pair of neighbouring elements have at least k=5k=5 difference between them.
In the second example the maximum k=0k=0, any order is 00-acceptable.
In the third example the given order is already 33-acceptable, you can leave it as it is.
제목:
n * m (n < = 16, m < = 1e4) 의 행렬 을 드 리 겠 습 니 다. 줄 의 순 서 를 다시 배열 하여 a11, a21,................................................
사고방식: 최소 치가 가장 크 고 첫 번 째 반응 은 2 점 이다.그러나 이 문제 의 데이터 범 위 를 보면 먼저 두 배열 로 두 줄 사이 의 '거리' (즉, 같은 열 에 대응 하 는 값 의 차 이 를 나타 내 는 절대 치 의 최소 치) 와 j 행위 의 첫 번 째 줄, i 행위 의 마지막 줄 의 '수미 거리' 를 미리 처리 하 는 것 이 분명 하 다.
그리고 n < = 16 을 보면 상 압 이 가능 합 니 다.어떻게 눌 러 요?분명히 i 는 0 으로 i 줄 이 아직 사용 되 지 않 았 음 을 나타 내 고 1 은 사용 한 것 이다.그리고 총 결 과 는 첫 줄, 마지막 줄 이 어느 두 줄 인지 와 관련 이 있어 서 기억 화 검색 을 할 수 있 습 니 다.
dp [zt] [dn] [d1] 은 상태 zt 를 표시 할 때 첫 번 째 행위 의 원래 배열 d1 줄, 현재 행위 의 원래 배열 dn 줄 의 최대 값 을 표시 합 니 다.
dfs 에서 i = 0 ~ n - 1 을 옮 겨 다 니 며 현재 마지막 줄 의 결 과 를 순서대로 열거 합 니 다.
주의:
첫 줄 을 정할 때 는 특 판 을 해 야 합 니 다. 초기 거 리 는 inf 이기 때문에 '거리' 배열 로 결 과 는 0 입 니 다.특 판 때 는 현재 마지막 줄 을 써 야 한다.
마지막 으로 채 울 때 주의해 야 할 답 은 '수미 거리' 이 므 로 특 판 이 필요 하 다.
구체 적 인 세부 사항 은 코드 참조:

#include
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=25;
const int maxm=10010;
int n,m,k;
int a[maxn][maxm];
int dis[maxn][maxn],dis2[maxn][maxn];
int dp[70000][maxn][maxn];
int ans,tmp,cnt;
int dfs(int zt,int dn,int d1)
{
    int &res=dp[zt][dn][d1];
    if(res!=-1) return res;
    int ct=0,ma=-inf,tmp;
    for(int i=0;i