oj.uz

Submission #1072325

# Submission time Handle Problem Language Result Execution time Memory
1072325 2024-08-23T17:05:20 Z dwuy The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 2 ms 6488 KB 
/**         - 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++;
        }
    }
}

bool ok(int mid){
    /// 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;

    /// 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;

    /// 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -