Submission #692031

#	Time	Username	Problem	Language	Result	Execution time	Memory
692031		Cookie197	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	832 ms	227176 KiB

joioi

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define endl "\n"
#define out(x) cout<< #x << " = " << x << endl
#define mp make_pair
#define mt(a,b,c,d) mp(mp(a,b),mp(c,d)) 

int arr[8][3003][3003],n,m,s=2e9,sx[8],sy[8];
bool check(int num){

    for (int z=0;z<=7;z++){
        if (z==1 || z==2 || z==5 || z==7) swap(n,m);
        int am = 0,an = 1e9,bm = 0,bn = 1e9, ok = true;
        
        int lim = m, safe = false;
        for (int i=1;i<=n;i++){
            int cut = 0;
            for (int j=1;j<=lim;j++){
                if (max(am, arr[z][i][j]) - s > num) break;
                cut++;
                am = max(am, arr[z][i][j]);
                if (arr[z][i][j] == s) safe = true;
            }
            lim = cut;

            //if (i == sx[z] && cut < sy[z] && !safe) {ok = false; break;}

            for (int j=cut+1;j<=m;j++){
                bm = max(bm, arr[z][i][j]), bn = min(bn, arr[z][i][j]);
            }
            if (bm - bn > num) {ok = false; break;}
        }
        if (z==1 || z==2 || z==5 || z==7) swap(n,m);
        if (ok && safe) return true;
    }
    return false;
}
signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            int x; cin>>x;
            arr[0][i][j] = x;
            arr[1][j][i] = x;
            arr[2][m-j+1][n-i+1] = x;
            arr[3][n-i+1][m-j+1] = x;
            arr[4][n-i+1][j] = x;
            arr[5][m-j+1][i] = x;
            arr[6][i][m-j+1] = x;
            arr[7][j][n-i+1] = x;
            s = min(s, x);
        }
    }

    for (int z=0;z<=7;z++) for (int i=1;i<=n;i++) for (int j=n;j>=1;j--) if (arr[z][i][j] == s) sx[z] = i, sy[z] = j;


    int left = 0, right = 1000000005;
    while(left < right){
        int mid = (left + right) >> 1;
        if (!check(mid)) left = mid+1;
        else right = mid;
    }
    cout<<left<<endl;
}

Compilation message (stderr)

joioi.cpp: In function 'bool check(int)':
joioi.cpp:19:20: warning: unused variable 'an' [-Wunused-variable]
   19 |         int am = 0,an = 1e9,bm = 0,bn = 1e9, ok = true;
      |                    ^~

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