Submission #224624

#TimeUsernameProblemLanguageResultExecution timeMemory
224624infinite_iqThe Kingdom of JOIOI (JOI17_joioi)C++14
0 / 100
157 ms16204 KiB
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <bits/stdc++.h> using namespace std; #define sqr 547 #define mid (l+r)/2 #define pb push_back #define ppb pop_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define ins insert #define era erase #define C continue #define mem(dp,i) memset(dp,i,sizeof(dp)) #define mset multiset #define all(x) x.begin(), x.end() typedef long long ll; typedef short int si; typedef long double ld; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; const ll inf=1e18; const ll mod=1e9+7; const ld pai=acos(-1); int n , m ; int a [2009][2009] , done [2009][2009] ; int yes ( int x ) { int mn = 1e9 , mx = -1e9 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( done [i][j] ) C ; mn = min ( mn , a [i][j] ) ; mx = max ( mx , a [i][j] ) ; } } return ( mx - mn <= x ) ; } int check1 ( int x ) { mem ( done , 0 ) ; int last = 1e9 , mx = -1e9 , mn = 1e9 ; for ( int i = 0 ; i < n ; i ++ ) { int crnt = 0 ; for ( int j = 0 ; j < m ; j ++ ) { if ( crnt == last ) break ; int MN = min ( mn , a [i][j] ) ; int MX = max ( mx , a [i][j] ) ; if ( MX - MN > x ) { last = crnt ; break ; } mn = MN ; mx = MX ; crnt ++ ; done [i][j] = 1 ; } } return yes ( x ) ; } int check2 ( int x ) { mem ( done , 0 ) ; int last = 1e9 , mx = -1e9 , mn = 1e9 ; for ( int i = n-1 ; i >=0 ; i -- ) { int crnt = 0 ; for ( int j = 0 ; j < m ; j ++ ) { if ( crnt == last ) break ; int MN = min ( mn , a [i][j] ) ; int MX = max ( mx , a [i][j] ) ; if ( MX - MN > x ) { last = crnt ; break ; } mn = MN ; mx = MX ; crnt ++ ; done [i][j] = 1 ; } } return yes ( x ) ; } int check3 ( int x ) { mem ( done , 0 ) ; return 0 ; } int check4 ( int x ) { mem ( done , 0 ) ; return 0 ; } int main () { cin >> n >> m ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { cin >> a [i][j] ; } } int l = -1 , r = 1e9 ; while ( r - l > 1 ) { if ( check1 ( mid ) || check2 ( mid ) || check3 ( mid ) || check4 ( mid ) ) r = mid ; else l = mid ; } cout << r << endl ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...