Submission #51534

#TimeUsernameProblemLanguageResultExecution timeMemory
51534huynhsmdThe Kingdom of JOIOI (JOI17_joioi)C++17
0 / 100
2 ms612 KiB
#include<bits/stdc++.h> using namespace std; const int N=2005; int n , m , ans1 , ans2; int a[N][N] , b[N][N] , Min1[N][N] , Max1[N][N] , Min2[N][N] , Max2[N][N]; bool check1(int mid , int n , int m){ for(int i = 1 ; i <= n ; ++ i){ int ok = 0; for(int j = 0 ; j < m ;++ j) if(Max1[i][j] - Min1[i][j] <= mid && Max2[i][j + 1] - Min2[i][j + 1] <= mid){ ok = 1; break; } if(!ok) return false; } return true; } int solve(int a[N][N] , int n , int m){ for(int i = 1 ; i <= n ; ++ i){ for(int j = 1 ; j <= m ;++ j){ if( j == 1) Min1[i][1] = Max1[i][1] = a[i][1]; else{ Min1[i][j] = min( Min1[i][j - 1] , a[i][j]); Max1[i][j] = max( Max1[i][j - 1] , a[i][j]); } } for(int j = n ; j > 0 ; -- j){ if( j == m) Min2[i][n] = Max2[i][n] = a[i][n]; else{ Min2[i][j] = min( Min2[i][j + 1] , a[i][j]); Max2[i][j] = max( Max2[i][j + 1] , a[i][j]); } } } /*for(int i = 1 ; i <= n ; ++ i){ for(int j = 1 ; j <= m ;++ j) cout << Min1[i][j] << ' ' << Max1[i][j] << " ? "; cout <<endl; } for(int i = 1 ; i <= n ; ++ i){ for(int j = 1 ; j <= m ;++ j) cout << Min2[i][j] << ' ' << Max2[i][j] << " ? "; cout <<endl; } cout <<endl; */ int l = 0, r = 1e9 , res = r; while(l <= r){ int mid = (l + r) / 2; bool kt = check1(mid , n , m); if(kt){ res = mid; r = mid - 1; } else l = mid + 1; } return res; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); //freopen("1.inp","r",stdin); cin >> n >> m; for(int i = 1 ; i <= n ; ++ i) for(int j = 1 ; j <= m ;++ j) cin >> a[i][j]; for(int j = 1 ; j <= m ; ++ j) for(int i = 1 ; i <= n ; ++ i) b[j][i] = a[i][j]; cout << max(solve(a , n , m) , solve(b , m , n) ); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...