제출 #1199493

#제출 시각아이디문제언어결과실행 시간메모리
1199493efishelThe Kingdom of JOIOI (JOI17_joioi)C++20
60 / 100
4083 ms327632 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vll = vector <ll>; using ii = pair <ll, ll>; using vii = vector <ii>; using lii = pair <ll, ii>; const ll INF = ll(1E18)+16; int main () { cin.tie(nullptr) -> sync_with_stdio(false); ll n, m; cin >> n >> m; vector <vll> mat(n, vll(m, 0)); for (vll &ve : mat) for (ll &i : ve) cin >> i; auto fgetAns = [&]() { lii maxN = { 0, { -15, -15 } }; for (ll i = 0; i < n; i++) { for (ll j = 0; j < m; j++) { maxN = max(maxN, { mat[i][j], { i, j } }); } } vector <vll> minX(n, vll(m, INF)); for (ll i = 0; i < n; i++) { for (ll 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'; } ll pans = INF; vector <lii> th; for (ll i = 0; i < n; i++) { for (ll j = 0; j < m; j++) { th.push_back({ minX[i][j], { i, j } }); } } multiset <ll> mst; // bottleneck for (ll i = 0; i < n; i++) { for (ll j = 0; j < m; j++) { mst.insert(mat[i][j]); } } ll base = minX[maxN.second.first][maxN.second.second]; sort(th.rbegin(), th.rend()); for (auto [val, ppair] : th) { auto [i, j] = ppair; base = min(base, val); assert(mst.size()); mst.erase(mst.find(mat[i][j])); if (mst.empty()) continue; // or break; pans = min(pans, max(maxN.first - base, *(mst.rbegin()) - *(mst.begin()))); } return pans; }; ll ans = INF; // cerr << fgetAns() << '\n'; ans = min(ans, fgetAns()); for (ll i = 0; i < n; i++) { for (ll j = 0; 2*j < m; j++) { swap(mat[i][j], mat[i][m-1-j]); } } // cerr << fgetAns() << '\n'; ans = min(ans, fgetAns()); for (ll i = 0; 2*i < n; i++) { for (ll j = 0; j < m; j++) { swap(mat[i][j], mat[n-1-i][j]); } } // cerr << fgetAns() << '\n'; ans = min(ans, fgetAns()); for (ll i = 0; i < n; i++) { for (ll 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...