CodeForces - 1102F Elongated Matrix [상압 DP]

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<=16이며 줄만 이동할 수 있기 때문에 열은 고정되어 있습니다.그럼 상태 압축을 고려해.
각 줄 사이의 인접한 차치(이것은 줄의 선후 순서와 무관)와 첫 줄과 마지막 줄의 차치(이것은 선후 순서와 관계가 있다)
dp[sta][top][now]
sta에서 1은 사용한 줄을 나타내고 0은 사용하지 않은 줄을 나타내며 top는 첫 번째 줄을 나타내고 now는 현재 열거된 줄을 나타낸다.
첫 번째 매거량은 첫 번째 줄 요소이고 순서대로 다른 줄을 추가합니다. 줄과 줄 사이의 차이를 유지하는 최소값은 ans에서 max를 찾으면 됩니다.
ffs 좀 쓰기 좋을 것 같아. 기억해 봐. 상태는 최대 1e7 정도야.
 
 
이번 div3 문제는 어렵지 않아요.다 할 것 같은데 엉뚱한 카드 이론 AK, 다 쓴 코드가 전부 BUG 천재 BUG 선수인데 코드 능력이 너무 약해서...
 

#include "bits/stdc++.h"
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
int a[20][10004];
int dis[20][20];
int tr[20][20];
int dp[1<<16][20][20];
int n,m;
int dfs(int sta,int top,int now)
{
    if(sta==(1<