Codeforces 1102F

 1 #include<bits/stdc++.h>
 2 #define maxs 70005
 3 #define maxn 18
 4 #define maxm 10005
 5 using namespace std;
 6 const int inf = (int)(1e9)+7;
 7 int n,m;
 8 int a[maxn][maxm];
 9 int w[maxn][maxn],nxtw[maxn][maxn];
10 int dp[maxn][maxs];
11 int main()
12 {
13     scanf("%d%d",&n,&m);
14     for(int i=1;i<=n;++i)
15         for(int j=1;j<=m;++j)scanf("%d",&a[i][j]);
16     for(int i=1;i<=n;++i)
17         for(int j=1;j<=n;++j)
18         {
19             w[i][j]=nxtw[i][j]=inf;
20             for(int k=1;k<=m;++k)w[i][j]=min(w[i][j],abs(a[i][k]-a[j][k]));
21             for(int k=1;k<m;++k)nxtw[i][j]=min(nxtw[i][j],abs(a[i][k]-a[j][k+1]));
22         }
23     int ans=0;
24     for(int st=0;st<n;++st)
25     {
26         memset(dp,0,sizeof(dp));
27         dp[st][1<<st]=inf;
28         for(int S=0;S<(1<<n);++S)
29         {
30             for(int i=0;i<n;++i)if(S&(1<<i))
31             {
32                 for(int j=0;j<n;++j)if(!(S&(1<<j)))dp[j][S|(1<<j)]=max(dp[j][S|(1<<j)],min(dp[i][S],w[i+1][j+1]));
33             }
34         }
35         for(int i=0;i<n;++i)ans=max(ans,min(dp[i][(1<<n)-1],nxtw[i+1][st+1]));
36     }
37     printf("%d\n",ans);
38 }