Submission #1265640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265640		axleofapulley	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	0 ms	324 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
int main(){
    int h, w; cin >> h >> w; int arr[h][w]; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) cin >> arr[i][j]; 
    pair<int, int> mnid, mxid; int mn=1e9+7, mx=0; 
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            mn=min(mn, arr[i][j]); mx=max(mx, arr[i][j]);
        }
    }
    int step=(mx-mn+1)/2; int ansmnt = 0, cpt=0;
    while(cpt<2){
        ansmnt += step; bool chosen[h][w]; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) chosen[i][j]=true;
        for(int i = 0; i < h; i++){
            if(i>0) if(chosen[i-1][0]) break;
            for(int j = 0; j < w; j++){
                if(arr[i][j]>mn+ansmnt) break;
                chosen[i][j]=false; 
            }
        }
        int tpmn = 1e9+7; 
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(chosen[i][j]) tpmn=min(tpmn, arr[i][j]);
            }
        }
        if(mx-tpmn<=ansmnt) step=-((abs(step)+1)/2); 
        else step=(abs(step)+1)/2;
        if(abs(step)==1) cpt++;
    }
    step=(mx-mn+1)/2; cpt = 0; int ansmxt = 0;
    while(cpt<2){
        ansmxt += step; bool chosen[h][w]; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) chosen[i][j]=true;
        for(int i = 0; i < h; i++){
            if(i>0) if(chosen[i-1][0]) break;
            for(int j = 0; j < w; j++){
                if(arr[i][j]<mx-ansmxt) break;
                chosen[i][j]=false; 
            }
        }
        int tpmx = 0; 
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(chosen[i][j]) tpmx=max(tpmx, arr[i][j]);
            }
        }
        if(tpmx-mn<=ansmxt) step=-((abs(step)+1)/2); 
        else step=(abs(step)+1)/2;
        if(abs(step)==1) cpt++;
    }
    step=(mx-mn+1)/2; cpt = 0; int ansmnb = 0;
    while(cpt<2){
        ansmnb += step; bool chosen[h][w]; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) chosen[i][j]=true;
        for(int i = h-1; i >= 0; i--){
            if(i<h-1) if(chosen[i+1][0]) break;
            for(int j = 0; j < w; j++){
                if(arr[i][j]>mn+ansmnb) break;
                chosen[i][j]=false; 
            }
        }
        int tpmn = 1e9+7; 
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(chosen[i][j]) tpmn=min(tpmn, arr[i][j]);
            }
        }
        if(mx-tpmn<=ansmnb) step=-((abs(step)+1)/2); 
        else step=(abs(step)+1)/2;
        if(abs(step)==1) cpt++;
    }
    step=(mx-mn+1)/2; cpt = 0; int ansmxb = 0;
    while(cpt<2){
        ansmxb += step; bool chosen[h][w]; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) chosen[i][j]=true;
        for(int i = h-1; i >= 0; i--){
            if(i<h-1) if(chosen[i+1][0]) break;
            for(int j = 0; j < w; j++){
                if(arr[i][j]<mx-ansmxb) break;
                chosen[i][j]=false; 
            }
        }
        int tpmx = 0; 
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(chosen[i][j]) tpmx=max(tpmx, arr[i][j]);
            }
        }
        if(tpmx-mn<=ansmxb) step=-((abs(step)+1)/2); 
        else step=(abs(step)+1)/2;
        if(abs(step)==1) cpt++;
    }
    int ans = min(min(ansmnt, ansmxt), min(ansmnb, ansmxb));
    cout << ans;
}

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