Submission #1084052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084052		May27_th	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	1 ms	352 KiB

joioi

#include<bits/stdc++.h>
 
using namespace std;
 
#define i64 long long
#define int long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

void Solve(void) {
  int H, W; cin >> H >> W;
  vector<vector<int>> a(H + 2, vector<int> (W + 2));
  vector<vector<int>> prefmxR(H + 2, vector<int> (W + 2, 0));
  vector<vector<int>> suffmxR(H + 2, vector<int> (W + 2, 0));
  vector<vector<int>> prefmxC(H + 2, vector<int> (W + 2, 0));
  vector<vector<int>> suffmxC(H + 2, vector<int> (W + 2, 0));

  vector<vector<int>> prefmnR(H + 2, vector<int> (W + 2, INT_MAX));
  vector<vector<int>> suffmnR(H + 2, vector<int> (W + 2, INT_MAX));
  vector<vector<int>> prefmnC(H + 2, vector<int> (W + 2, INT_MAX));
  vector<vector<int>> suffmnC(H + 2, vector<int> (W + 2, INT_MAX));

  for (int i = 1; i <= H; i ++) {
    for (int j = 1; j <= W; j ++) {
      cin >> a[i][j];
      prefmxR[i][j] = max(a[i][j], prefmxR[i][j - 1]);
      prefmnR[i][j] = min(a[i][j], prefmnR[i][j - 1]);
    }
    for (int j = W; j >= 1; j --) {
      suffmxR[i][j] = max(a[i][j], suffmxR[i][j + 1]);
      suffmnR[i][j] = min(a[i][j], suffmnR[i][j + 1]);
    }
  }

  for (int j = 1; j <= W; j ++) {
    for (int i = 1; i <= H; i ++) {
      prefmxC[i][j] = max(a[i][j], prefmxC[i - 1][j]);
      prefmnC[i][j] = min(a[i][j], prefmnC[i - 1][j]);
    }
    for (int i = H; i >= 1; i --) {
      suffmxC[i][j] = max(a[i][j], suffmxC[i + 1][j]);
      suffmnC[i][j] = min(a[i][j], suffmnC[i + 1][j]);
    }
  }

  auto check = [&](int gap) {
    for (int i = 1; i <= H; i ++) {
      for (int j = 1; j <= W; j ++) {
        bool workslf = true, worksrg = true;
        if (abs(a[i][j] - prefmnR[i][j]) > gap) workslf = false;
        if (abs(a[i][j] - prefmxR[i][j]) > gap) workslf = false;
        
        if (abs(a[i][j] - suffmnR[i][j]) > gap) worksrg = false;
        if (abs(a[i][j] - suffmxR[i][j]) > gap) worksrg = false;

        if (!(workslf | worksrg)) return false;
      }
    }

    for (int j = 1; j <= W; j ++) {
      for (int i = 1; i <= H; i ++) {
        bool workslf = true, worksrg = true;
        if (abs(a[i][j] - prefmnC[i][j]) > gap) workslf = false;
        if (abs(a[i][j] - prefmxC[i][j]) > gap) workslf = false;
        
        if (abs(a[i][j] - suffmnC[i][j]) > gap) worksrg = false;
        if (abs(a[i][j] - suffmxC[i][j]) > gap) worksrg = false;

        if (!(workslf | worksrg)) return false;
      }
    }

    return true;
  }; 

  int l = 0, h = 1000000000;
  while (l <= h) {
    int mid = (l + h)/2;
    if (check(mid)) h = mid - 1;
    else l = mid + 1;
  }
  cout << l << "\n";
}

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int Tests = 1; // cin >> Tests; 
  while (Tests --) {
    Solve();    
  }
}

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