제출 #631201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631201		Abrar_Al_Samit	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1304 ms	70572 KiB

joioi

#include<bits/stdc++.h>
using namespace std;

const int MX = 2005;
const int INF = 1e9;

int a[MX][MX];
int n, m;
int mn, mx;
int mark[MX][MX];

bool can(int ans, bool tag) {
  for(int i=0; i<n; ++i) {
    for(int j=0; j<m; ++j) {
      mark[i][j] = -1;
      if(a[i][j]-mn>ans) {
        mark[i][j] = tag;
      }
      if(mx-a[i][j]>ans) {
        if(mark[i][j]!=-1) return false;
        mark[i][j] = tag^1;
      }
    }
  }

  auto LEFT_RIGHT_DIAGONAL = [&] () {
    int prev = INF;
    for(int i=0; i<n; ++i) {
      int upto = m;
      bool zero = false;
      for(int j=m-1; j>-1; --j) {
        if(mark[i][j]==0) {
          zero = true;
          if(j>prev) return false;
          continue;
        }
        if(mark[i][j]==1) {
          if(zero) return false;
          upto = j;
        }
      }
      prev = min(prev, upto-1);
    }
    return true;
  };
  auto RIGHT_LEFT_DIAGONAL = [&] () {
    int prev = -1;
    for(int i=0; i<n; ++i) {
      int upto = -1;
      bool one = false;
      for(int j=0; j<m; ++j) {
        if(mark[i][j]==1) {
          one = true;
          if(j<prev) return false;
          continue;
        }
        if(mark[i][j]==0) {
          if(one) return false;
          upto = j;
        }
      }
      prev = max(prev, upto+1);
    }
    return true;
  };
  return (LEFT_RIGHT_DIAGONAL()|(RIGHT_LEFT_DIAGONAL()));
}
void PlayGround() {
  cin>>n>>m;
  mx = -1, mn = INF;
  for(int i=0; i<n; ++i) {
    for(int j=0; j<m; ++j) {
      cin>>a[i][j];
      mn = min(mn, a[i][j]);
      mx = max(mx, a[i][j]);
    }
  }

  int l = 0, r = 1e9;
  while(l<r) {
    int mid = (l+r)/2;
    if(can(mid, 0) || can(mid, 1)) r = mid;
    else l = mid+1;
  }
  cout<<l<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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