Submission #1129127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129127		Newtonabc	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	1603 ms	16152 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > tb;
int n,m,mn=INT_MAX;
int cal(){
    int l=0,r=INT_MAX;
    while(l<r){
        int mid=(l+r)/2,midx=INT_MAX,low=INT_MAX,high=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mn+mid<tb[i][j]){
                    midx=min(midx,j);
                }
                if(j>=midx){
                    low=min(low,tb[i][j]);
                    high=max(high,tb[i][j]);
                }
            }
        }
        if(high-low<=mid) r=mid;
        else l=mid+1;
    }
    return l;
}
int main(){
    cin>>n >>m;
    int ans=INT_MAX;
    tb.resize(n,vector<int>(m,0));
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>tb[i][j],mn=min(mn,tb[i][j]);
    ans=min(ans,cal());
    reverse(tb.begin(),tb.end());
    ans=min(ans,cal());
    for(int i=0;i<n;i++) reverse(tb[i].begin(),tb[i].end());
    ans=min(ans,cal());
    reverse(tb.begin(),tb.end());
    ans=min(ans,cal());
    cout<<ans;
} 

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