oj.uz

Submission #1084051

# Submission time Handle Problem Language Result Execution time Memory
1084051 2024-09-05T02:06:16 Z May27_th The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 352 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define i64 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 = 1, 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 352 KB Output isn't correct
2 Halted 0 ms 0 KB -