Submission #1235803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235803		Geforgs	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	645 ms	157712 KiB

joioi

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
//#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;

bool check(ll x, ll n, ll m, vector<vector<ll>>& val, vector<vector<ll>>& a, vector<vector<ll>>& b, vector<vector<ll>>& c, vector<vector<ll>>& d){
    ll mi=inf, k=a[n][m], A=0, B=0, C=0, D=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(val[i][j] + x < k){
                mi = min(mi, val[i][j]);
                A = max(A, a[i][j]);
                B = max(B, b[i][j]);
                C = max(C, c[i][j]);
                D = max(D, d[i][j]);
            }
        }
    }
    if(mi + x < min({A, B, C, D})){
        return true;
    }
    return false;
}

void solve(){
    ll n, m, i, j, l=0, r=1e9, mid;
    cin>>n>>m;
    vector<vector<ll>> val(n+2, vector<ll>(m+2));
    vector<vector<ll>> a(n+2, vector<ll>(m+2));
    vector<vector<ll>> b(n+2, vector<ll>(m+2));
    vector<vector<ll>> c(n+2, vector<ll>(m+2));
    vector<vector<ll>> d(n+2, vector<ll>(m+2));
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j){
            cin>>val[i][j];
        }
    }
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j){
            a[i][j] = max({val[i][j], a[i-1][j], a[i][j-1]});
        }
        for(j=m;j>=1;--j){
            b[i][j] = max({val[i][j], b[i-1][j], b[i][j+1]});
        }
    }
    for(i=n;i>=1;--i){
        for(j=1;j<=m;++j){
            c[i][j] = max({val[i][j], c[i+1][j], c[i][j-1]});
        }
        for(j=m;j>=1;--j){
            d[i][j] = max({val[i][j], d[i+1][j], d[i][j+1]});
        }
    }
    while(r - l > 1){
        mid = (l+r)/2;
        if(check(mid, n, m, val, a, b, c, d)){
            l = mid;
        }else{
            r = mid;
        }
    }
    cout<<r<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(nullptr));
    ll t=1;
//    cin>>t;
    for(;t>0;--t){
        solve();
    }
    return 0;
}

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