제출 #532645

#제출 시각아이디문제언어결과실행 시간메모리
532645ioiThe Kingdom of JOIOI (JOI17_joioi)C++14
15 / 100
4080 ms872 KiB
#include<bits/stdc++.h> using namespace std; #define debug(x) cout << '[' << #x << " is: " << x << "] " << endl; #define inF freopen("6in.txt" , "r" , stdin); #define outF freopen("6.txt" , "w" , stdout); #define imod(a , n) (a % n + n ) % n #define sor(v) sort(v.begin() , v.end()); #define print(v) for(auto f : v ) cout << f << " " ; #define rsor(v) sort(v.rbegin() , v.rend()); #define rev(v) reverse(v.begin() , v.end()); #define scan(v)for(auto &it : v)cin >> it ; #define ll long long //#define int ll #define logar(x , y) log(x) / log(y) #define __sum(n) n * (n + 1) / 2 #define __lcm(a , b) a / __gcd(a , b) * b #define pii pair<int , int > #define fastio ios_base::sync_with_stdio(false);cin.tie(0); const int N = 1e3 + 5 , M = N * 64 , MX = 2e4 + 40; const ll MOD = 1e9 + 7 , oo = 1e9 + 9 , OO = 1e18 , mod = MOD ; const double pi = acos(-1) , eps = 1e-17 ; int di[] = {1 , -1 , 0 , 0}; int dj[] = {0 , 0 , -1 , 1}; int32_t main() { //inF; //inF;outF; fastio; int n , m ; cin >> n >> m ; set<int> st ; vector<ll>v(n*m); for(auto &it : v){cin >> it ; st.insert(it); } ll arr[n][m]; for(int i = 0 ; i < n ; i ++) for(int j = 0 ; j < m ; j ++) arr[i][j] = v[i * m + j]; v.clear(); for(auto it: st)v.push_back(it); int sz = n * m ; ll mnans = 1e18 ; int i = 0; for(int j = i ; j < sz ; j ++){ int en = n ; ll mn = 1e18 , mx = 0 ; //if(v[i] != 8 || v[j] != 26)continue ; for(int c = 0 ; c < m ; c ++){ for(int r = 0 ; r < n ; r ++){ if(arr[r][c] > v[j] || arr[r][c] < v[i]){ en = min(en , r) ; } // debug(en) if(r >= en)mn = min(mn , arr[r][c]) , mx = max(mx , arr[r][c]); } // if(v[i] == 8 && v[j] == 26)debug(en) // debug(en) } mnans = min(mnans , max(mx - mn , v[j] - v[i])); en = n ; mn = 1e18 , mx = 0 ; for(int c = m - 1 ; c >= 0; c --){ for(int r = 0 ; r < n ; r ++){ if(arr[r][c] > v[j] || arr[r][c] < v[i]){ en = min(en , r) ; } // debug(en) if(r >= en)mn= min(mn , arr[r][c]), mx = max(mx , arr[r][c]); } // if(v[i] == 8 && v[j] == 26)debug(en) // debug(en) } mnans = min(mnans , max(mx - mn , v[j] - v[i])); } i = sz - 1; for(int j = i ; j >= 0 ; j --){ int en = n ; ll mn = 1e18 , mx = 0 ; // if(v[j] != 10)continue ; //if(v[i] != 8 || v[j] != 26)continue ; for(int c = 0 ; c < m ; c ++){ for(int r = 0 ; r < n ; r ++){ if(arr[r][c] < v[j] || arr[r][c] > v[i]){ en = min(en , r) ; } // debug(en) if(r >= en)mn = min(mn , arr[r][c]) , mx = max(mx , arr[r][c]); } // if(v[i] == 8 && v[j] == 26)debug(en) // debug(en) } mnans = min(mnans , max(mx - mn , -v[j] + v[i])); en = n ; mn = 1e18 , mx = 0 ; for(int c = m - 1 ; c >= 0; c --){ for(int r = 0 ; r < n ; r ++){ if(arr[r][c] < v[j] || arr[r][c] > v[i]){ en = min(en , r) ; } // debug(en) if(r >= en)mn= min(mn , arr[r][c]), mx = max(mx , arr[r][c]); } // if(v[i] == 8 && v[j] == 26)debug(en) // debug(en) } // debug(mn) mnans = min(mnans , max(mx - mn , -v[j] + v[i])); } cout << mnans ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...