Submission #167921

#	Time	Username	Problem	Language	Result	Execution time	Memory
167921		theStaticMind	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	792 ms	70424 KiB

joioi

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
int n,m;
int mx=-INF,mn=INF;
bool solve(vector<vector<int>>&arr,int x,int y){
      int Y=m;
      vector<int> lim(n,0);
      for(int i=0;i<n;i++){
            for(int j=0;j<Y;j++){
                  if(arr[i][j]>x)Y=j;
            }
            lim[i]=Y;
      }
      for(int i=n-1;i>=0;i--){
            for(int j=m-1;j>=lim[i];j--){
                  if(arr[i][j]<y)return false;
            }
      }
      return true;
}
int binary_search(vector<vector<int>>& arr){
      int l=0,r=mx-mn,ans=INF;
      while(l<=r){
            int mid=(l+r)/2;
            if(solve(arr,mn+mid,mx-mid)){
                  ans=min(ans,mid);
                  r=mid-1;
            }
            else l=mid+1;
      }
      return ans;
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      cin>>n>>m;
      vector<vector<int>>arr(n,vector<int>(m));
      for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                  cin>>arr[i][j];
                  int x=arr[i][j];
                  mn=min(mn,x);
                  mx=max(mx,x);
            }
      }
      int ans=INF;
      ans=min(ans,binary_search(arr));
      reverse(all(arr));
      ans=min(ans,binary_search(arr));
      for(int i=0;i<n;i++)reverse(all(arr[i]));
      ans=min(ans,binary_search(arr));
      reverse(all(arr));
      ans=min(ans,binary_search(arr));
      cout<<ans;
}

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