Submission #1072339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072339		dwuy	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1438 ms	184660 KiB

joioi

/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MX = 2005;

int n, m;
int mxvalue, mnvalue;
int a[MX][MX];
bool f[MX][MX];
pii f1[MX][MX];
pii f2[MX][MX];
pii f3[MX][MX];
pii f4[MX][MX];

void nhap(){
    cin >> n >> m;
    // cin.ignore();
    // for(int i=1; i<=n; i++){
    //     string s; getline(cin, s); s += ' ';
    //     for(int j=0, t=1; j<len(s); j++) if(s[j] != ' '){
    //         a[i][t] = a[i][t]*10 + s[j] - '0';
    //         if(s[j + 1] == ' ') t++;
    //     }
    // }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
        }
    }
}

bool ok(int mid){
    memset(f, 0, sizeof f);
    /// case 1
    /// X O
    /// O O
    for(int i=1; i<=n; i++){
        for(int j=m; j>=0; j--){
            f[i][j] = f[i][j+1] | ((i == 1 || f[i-1][j]) && f1[i][j].se <= mnvalue + mid && f4[i][j+1].fi >= mxvalue - mid);
        }
    }
    if(f[n][0]) return 1;
    
    memset(f, 0, sizeof f);
    /// case 2
    /// O X
    /// O O
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m+1; j++){
            f[i][j] = f[i][j-1] | ((i == 1 || f[i-1][j]) && f2[i][j].se <= mnvalue + mid && f3[i][j-1].fi >= mxvalue - mid);
        }
    }
    if(f[n][m+1]) return 1;
    
    memset(f, 0, sizeof f);
    /// case 3
    /// O O
    /// X O
    for(int i=n; i>=1; i--){
        for(int j=m; j>=0; j--){
            f[i][j] = f[i][j+1] | ((i == n || f[i+1][j]) && f3[i][j].se <= mnvalue + mid && f2[i][j+1].fi >= mxvalue - mid);
        }
    }
    if(f[1][0]) return 1;

    memset(f, 0, sizeof f);
    /// case 4
    /// O O
    /// O X
    for(int i=n; i>=1; i--){
        for(int j=1; j<=m+1; j++){
            f[i][j] = f[i][j-1] | ((i == n || f[i+1][j]) && f4[i][j].se <= mnvalue + mid && f1[i][j-1].fi >= mxvalue - mid);
        }
    }
    if(f[1][m+1]) return 1;

    return 0;
}

pii combine(pii a, pii b){
    return {min(a.fi, b.fi), max(a.se, b.se)};
}

void solve(){
    for(int i=0; i<=n+1; i++){
        for(int j=0; j<=m+n; j++){
            f1[i][j] = f2[i][j] = f3[i][j] = f4[i][j] = {INF, -INF};
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            f1[i][j] = combine(combine(f1[i-1][j], f1[i][j-1]), {a[i][j], a[i][j]});
        }
        for(int j=m; j>=1; j--){
            f2[i][j] = combine(combine(f2[i-1][j], f2[i][j+1]), {a[i][j], a[i][j]});
        }
    }
    for(int i=n; i>=1; i--){
        for(int j=1; j<=m; j++){
            f3[i][j] = combine(combine(f3[i+1][j], f3[i][j-1]), {a[i][j], a[i][j]});
        }
        for(int j=m; j>=1; j--){
            f4[i][j] = combine(combine(f4[i+1][j], f4[i][j+1]), {a[i][j], a[i][j]});
        }
    }
    
    mnvalue = f1[n][m].first;
    mxvalue = f1[n][m].second;

    int res = -1;
    for(int lo=1, hi=1e9; lo<=hi;){
        int mid = (lo + hi)>>1;
        if(ok(mid)) res = mid, hi = mid - 1;
        else lo = mid + 1;
    }

    cout << res;
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40