제출 #322431

#제출 시각아이디문제언어결과실행 시간메모리
322431SeanliuThe Kingdom of JOIOI (JOI17_joioi)C++17
60 / 100
2791 ms262148 KiB
#include <iostream> #include <algorithm> #include <utility> #include <vector> #define ericxiao ios_base::sync_with_stdio(0);cin.tie(0); #define pii pair<int,int> #define F first #define S second using namespace std; const int maxN = 2e3 + 326, INF = 2e9 + 326; int N, M, arr[maxN][maxN], cnt[maxN * maxN], sz; vector<int> lisan; vector<pii> pos[maxN * maxN]; bool vis[maxN][maxN]; void take(int y, int x, int &mx, int &mn, int d){ if(d == 0){ for(int i = y; i >= 0 && !vis[i][x]; i--){ for(int j = x; j >= 0 && !vis[i][j]; j--){ vis[i][j] = true; cnt[arr[i][j]]--; mx = max(mx, arr[i][j]); mn = min(mn, arr[i][j]); } } } else if(d == 1){ for(int i = y; i < N && !vis[i][x]; i++){ for(int j = x; j >= 0 && !vis[i][j]; j--){ vis[i][j] = true; cnt[arr[i][j]]--; mx = max(mx, arr[i][j]); mn = min(mn, arr[i][j]); } } } else if(d == 2){ for(int i = y; i < N && !vis[i][x]; i++){ for(int j = x; j < M && !vis[i][j]; j++){ vis[i][j] = true; cnt[arr[i][j]]--; mx = max(mx, arr[i][j]); mn = min(mn, arr[i][j]); } } } else if(d == 3){ for(int i = y; i >= 0 && !vis[i][x]; i--){ for(int j = x; j < M && !vis[i][j]; j++){ vis[i][j] = true; cnt[arr[i][j]]--; mx = max(mx, arr[i][j]); mn = min(mn, arr[i][j]); } } } } inline void rot(){ for(int i = 0; i < sz; i++){ cnt[i] = 0; } for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) { vis[i][j] = false; cnt[arr[i][j]]++; } } int main(){ ericxiao; cin >> N >> M; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cin >> arr[i][j]; lisan.push_back(arr[i][j]); } } sort(lisan.begin(), lisan.end()); sz = unique(lisan.begin(), lisan.end()) - lisan.begin(); for(int i = 0; i < N; i++) for(int j = 0; j < M; j++){ arr[i][j] = lower_bound(lisan.begin(), lisan.begin() + sz, arr[i][j]) - lisan.begin(); cnt[arr[i][j]]++; pos[arr[i][j]].emplace_back(i, j); } int ans = lisan[sz - 1] - lisan[0]; for(int jizz = 0; jizz < 4; jizz++){ //cout << "in jizz = " << jizz << endl; int mx = -INF, mn = INF, f = 0, e = sz - 1; for(int i = 0; i < sz; i++){ //take all of them // //cout << "i = " << i << ", = " << lisan[i] << endl; for(auto [y, x] : pos[i]){ take(y, x, mx, mn, jizz); } /* for(int y = 0; y < N; y++) for(int x = 0; x < M; x++){ cout << vis[y][x] << " \n"[x == M - 1]; } */ while(f < sz - 1 && !cnt[f]) f++; while(e && !cnt[e]) e--; if(f == sz || !e) break; ans = min(ans, max(lisan[e] - lisan[f], lisan[mx] - lisan[mn])); //cout << "ans = " << ans << endl; } rot(); } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...