Submission #1298952

#TimeUsernameProblemLanguageResultExecution timeMemory
1298952IcelastThe Kingdom of JOIOI (JOI17_joioi)C++20
100 / 100
394 ms47628 KiB
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 2e9;
void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n+1, vector<int>(m+1));
    int S = INF, L = -INF;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            S = min(S, a[i][j]);
            L = max(L, a[i][j]);
        }
    }
    auto rtate = [&](vector<vector<int>> &a) -> void{
        int n = a.size()-1, m = a[0].size()-1;
        vector<vector<int>> b(m+1, vector<int>(n+1));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                b[j][n-i+1] = a[i][j];
            }
        }
        a = b;
    };
    int ans = L - S;
    auto sf = [&]() -> int{
        int n = a.size() - 1, m = a[0].size()-1;
        vector<int> f(m+1, INF), pf(m+1, INF);
        vector<int> pfa(m+1, 0), sfa(m+2, 0);
        vector<int> rS(n+1, 0), lL(n+1, m+1);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(a[i][j] == S){
                    rS[i] = max(rS[i], j);
                }
                if(a[i][j] == L){
                    lL[i] = min(lL[i], j);
                }
            }
        }
        f[0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                pfa[j] = max(pfa[j-1], a[i][j] - S);
            }
            for(int j = m; j >= 1; j--){
                sfa[j] = max(sfa[j+1], L - a[i][j]);
            }
            pf[0] = f[0];
            f[0] = INF;
            for(int j = 1; j <= m; j++){
                pf[j] = min(pf[j-1], f[j]);
                f[j] = INF;
            }
            for(int j = rS[i]; j < lL[i]; j++){
                f[j] = max(pf[j], max(pfa[j], sfa[j+1]));
            }
        }
        int res = INF;
        for(int j = 1; j <= m; j++){
            res = min(res, f[j]);
        }
        return res;
    };
    for(int it = 0; it < 4; it++){
        if(it > 0){
            rtate(a);
        }
        ans = min(ans, sf());
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...