Submission #854555

#	Time	Username	Problem	Language	Result	Execution time	Memory
854555		NeroZein	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2323 ms	56096 KiB

joioi

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  int mx = 0; 
  vector<vector<int>> a(n, vector<int> (m)); 
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cin >> a[i][j];
      mx = max(mx, a[i][j]); 
    }
  }
  auto check = [&](int mid) {
    int la = m - 1;
    int min_val = mx - mid; 
    vector<vector<bool>> region(n, vector<bool> (m)); 
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= la; ++j) {//coli <= coli-1
        if (a[i][j] < min_val) {
          la = j - 1;
          break; 
        }
        region[i][j] = 1;
      }
    }
    vector<int> bmx(2), bmn(2, 1e9); 
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        bmx[region[i][j]] = max(bmx[region[i][j]], a[i][j]);
        bmn[region[i][j]] = min(bmn[region[i][j]], a[i][j]);
      }
    }
    return max(bmx[0] - bmn[0], bmx[1] - bmn[1]) <= mid; 
  };
  auto solve = [&]() {
    int l = 0, r = 1e9;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid)) {
        r = mid;
      } else {
        l = mid + 1; 
      }
    }
    return l; 
  };
  auto flip_rows = [&]() {
    for (int i = 0; i < n / 2; ++i) {
      for (int j = 0; j < m; ++j) {
        swap(a[i][j], a[n - i - 1][j]); 
      }
    }
  }; 
  auto flip_cols = [&]() {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m / 2; ++j) {
        swap(a[i][j], a[i][m - j - 1]); 
      }
    }
  };
  int ans = solve(); //0, 0
  flip_cols();
  ans = min(ans, solve()); //0, 1
  flip_rows();
  ans = min(ans, solve()); //1, 1
  flip_cols();
  ans = min(ans, solve());//1, 0
  cout << ans << '\n'; 
  return 0;
}

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