oj.uz

Submission #631192

# Submission time Handle Problem Language Result Execution time Memory
631192 2022-08-17T19:14:58 Z Abrar_Al_Samit The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 26 ms 32340 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 32340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 32340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 32340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -