제출 #631192

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

joioi

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

const int MX = 2005;

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

bool can(int ans, bool tag) {
  memset(mark, -1, sizeof mark);

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

  auto LEFT_RIGHT_DIAGONAL = [&] () {
    int prev = INT_MAX;
    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;
          continue;
        }
        if(mark[i][j]==1) {
          if(zero) return false;
          upto = j;
        }
      }
      for(int j=prev+1; j<m; ++j) {
        if(mark[i][j]==0) return false;
      }
      prev = upto;
    }
    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;
          continue;
        }
        if(mark[i][j]==0) {
          if(one) return false;
          upto = j;
        }
      }
      for(int j=prev-1; j>-1; --j) {
        if(mark[i][j]==1) return false;
      }
      prev = upto;
    }
    return true;
  };
  return (LEFT_RIGHT_DIAGONAL()|(RIGHT_LEFT_DIAGONAL()));
}
void PlayGround() {
  cin>>n>>m;
  mx = -1, mn = INT_MAX;
  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: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40