Submission #1143732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143732		fryingduc	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	1750 ms	16148 KiB

joioi

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2005;
const int movex[] = {1, -1, 0, 0};
const int movey[] = {0, 0, 1, -1};
int n, m, a[maxn][maxn];
int mr, mc;
bool vis[maxn][maxn];
bool region[maxn][maxn];

bool check(int mid) {
  int mn = 1e9, mx = -1;
  int l = n;
  for(int j = 1; j <= m; ++j) {
    for(int i = 1; i <= l; ++i) {
      if(a[i][j] - a[mr][mc] > mid) {
        l = i - 1;
        break;
      }
    }
    for(int i = l + 1; i <= n; ++i) {
      mn = min(mn, a[i][j]);
      mx = max(mx, a[i][j]);
    }
  }
  if(mx == -1 || mx - mn <= mid) return 1;
  return 0;
}

void solve() {
  cin >> n >> m;
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= m; ++j) {
      cin >> a[i][j];
    }
  }
  int res = 1e9;
  for(int ix = 0; ix < 2; ++ix) {
    for(int iy = 0; iy < 2; ++iy) {
      for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
          if(!mr || a[i][j] < a[mr][mc]) {
            mr = i, mc = j;
          }
        }
      }
      int l = 0, r = res;
      while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
          res = mid;
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      }  
      for(int i = 1; i <= n; ++i) {
        reverse(a[i] + 1, a[i] + m + 1);
      }
    }
    for(int j = 1; j <= m; ++j) {
      for(int i = 1; i <= n / 2; ++i) {
        swap(a[i][j], a[n - i + 1][j]);
      }
    }
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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