Submission #751572

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

joioi

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

void solve() {
  int H, W;
  cin >> H >> W;
  vector<vector<int>> A(H, vector<int>(W));
  vector<pair<int, int>> P;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      P.emplace_back(i, j);
      cin >> A[i][j];
    } 
  }
  sort(P.begin(), P.end(), [&](pair<int, int> x, pair<int, int> y) {
    return A[x.first][x.second] < A[y.first][y.second];
  });
  vector<vector<int>> x(H, vector<int>(W + 1));
  for (int i = 0; i < H; i++) {
    x[i][W] = INT_MAX;
    for (int j = W - 1; j >= 0; j--) {
      x[i][j] = min(x[i][j + 1], A[i][j]);
    }
  }
  multiset<int> Spref, Ssuff;
  for (int i = 0; i < H; i++) {
    Spref.insert(x[i][0]);
    Ssuff.insert(x[i][0]);
  }
  vector<int> height(H), pref(H), suff(H);
  vector<vector<bool>> used(H, vector<bool>(W, false));
  int ans = A[P.back().first][P.back().second] - A[P[0].first][P[0].second];
  P.pop_back();
  for (auto [u, v] : P) {
    used[u][v] = true;
    for (int j = height[u]; j < W; j++) {
      if (!used[u][j]) {
        break;
      }
      height[u]++;
    }
    int p = u == 0 ? INT_MAX : pref[u - 1];
    for (int j = u; j < H; j++) {
      p = min(p, height[j]);
      if (pref[j] == p) {
        break;
      }
      Spref.erase(Spref.find(x[j][pref[j]]));
      pref[j] = p;
      Spref.insert(x[j][pref[j]]);
    }
    int s = u == H - 1 ? INT_MAX : suff[u + 1];
    for (int j = u; j >= 0; j--) {
      s = min(s, height[j]);
      if (suff[j] == s) {
        break;
      }
      Ssuff.erase(Ssuff.find(x[j][suff[j]]));
      suff[j] = s;
      Ssuff.insert(x[j][suff[j]]);
    }
    ans = min(ans, max(A[u][v] - A[P[0].first][P[0].second], A[P.back().first][P.back().second] - max(*Spref.begin(), *Ssuff.begin())));
  }
  cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

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