Submission #1265658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265658		axleofapulley	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	1294 ms	19976 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;
    while(step>0){
        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;
                if(i>0) if(chosen[i-1][j]) 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) ansmnt-=step;
        if(step==1) break;
        step=(step+1)/2;
    }
    step=(mx-mn+1)/2; int ansmxt = 0;
    while(step>0){
        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;
                if(i>0) if(chosen[i-1][j]) 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) ansmxt-=step;
        if(step==1) break;
        step=(step+1)/2;
    }
    step=(mx-mn+1)/2; int ansmnb = 0;
    while(step>0){
        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;
                if(i<h-1) if(chosen[i+1][j]) 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) ansmnb-=step;
        if(step==1) break;
        step=(step+1)/2;
    }
    step=(mx-mn+1)/2; int ansmxb = 0;
    while(step>0){
        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;
                if(i<h-1) if(chosen[i+1][j]) 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) ansmxb-=step;
        if(step==1) break;
        step=(step+1)/2; 
    }
    int ans = min(min(ansmnt, ansmxt), min(ansmnb, ansmxb))+1;
    cout << ans;
}

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