Submission #1199497

#TimeUsernameProblemLanguageResultExecution timeMemory
1199497efishelThe Kingdom of JOIOI (JOI17_joioi)C++20
100 / 100
3843 ms130056 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector <int>; using ii = pair <int, int>; using vii = vector <ii>; using lii = pair <int, ii>; const int INF = 1E9+16; const int MAXN = 2E3+16; int mat[MAXN][MAXN]; int minX[MAXN][MAXN]; bool vis[MAXN][MAXN]; int main () { cin.tie(nullptr) -> sync_with_stdio(false); ll n, m; cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> mat[i][j]; } } vector <lii> th, th2; auto fgetAns = [&]() { lii maxN = { 0, { -15, -15 } }; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { maxN = max(maxN, { mat[i][j], { i, j } }); } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { minX[i][j] = min((i == 0 ? INF : minX[i-1][j]), (j == 0 ? INF : minX[i][j-1])); minX[i][j] = min(minX[i][j], mat[i][j]); // cerr << mat[i][j] << ' '; } // cerr << '\n'; } int pans = INF; th.clear(); th2.clear(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { vis[i][j] = false; th.push_back({ minX[i][j], { i, j } }); th2.push_back({ mat[i][j], { i, j } }); } } int cl = 0, cr = n*m-1; int base = minX[maxN.second.first][maxN.second.second]; sort(th.rbegin(), th.rend()); sort(th2.begin(), th2.end()); for (auto [val, ppair] : th) { auto [i, j] = ppair; base = min(base, val); vis[i][j] = true; while (vis[th2[cr].second.first][th2[cr].second.second]) cr--; while (vis[th2[cl].second.first][th2[cl].second.second]) cl++; pans = min(pans, max(maxN.first - base, th2[cr].first - th2[cl].first)); if (cl == cr) break; } return pans; }; int ans = INF; // cerr << fgetAns() << '\n'; ans = min(ans, fgetAns()); for (int i = 0; i < n; i++) { for (int j = 0; 2*j < m; j++) { swap(mat[i][j], mat[i][m-1-j]); } } // cerr << fgetAns() << '\n'; ans = min(ans, fgetAns()); for (int i = 0; 2*i < n; i++) { for (int j = 0; j < m; j++) { swap(mat[i][j], mat[n-1-i][j]); } } // cerr << fgetAns() << '\n'; ans = min(ans, fgetAns()); for (int i = 0; i < n; i++) { for (int j = 0; 2*j < m; j++) { swap(mat[i][j], mat[i][m-1-j]); } } // cerr << fgetAns() << '\n'; ans = min(ans, fgetAns()); cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...