제출 #321665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
321665		casperwang	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	858 ms	117740 KiB

joioi

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

const int MAXN = 2000;
const int INF = 1e9;
int n, m;
int a[MAXN+1][MAXN+1];
int tmp[MAXN+1][MAXN+1];
int pre[MAXN+1][MAXN+1];
int suf_mmax[MAXN+2][MAXN+2];
int suf_mmin[MAXN+2][MAXN+2];
int R[MAXN+1];
int mmin;
int ans;

bool solve(int n, int m, int val) {
  for (int i = 1; i <= n; i++) {
    R[i] = upper_bound(pre[i]+1, pre[i]+1+m, mmin+val) - pre[i] - 1;
    if (i > 1) R[i] = min(R[i], R[i-1]);
  }
  if (!R[1]) return false;
  int _mmax = 0, _mmin = INF;
  for (int i = 1; i <= n; i++) {
    _mmax = max(_mmax, suf_mmax[i][R[i]+1]);
    _mmin = min(_mmin, suf_mmin[i][R[i]+1]);
  }
  if (_mmax - _mmin > val) return false;
  return true;
}

int cal(int n, int m) {
  int l = 0, r = 1e9, mid;
  while (l < r) {
    mid = l + r >> 1;
    if (!solve(n, m, mid))
      l = mid + 1;
    else
      r = mid;
  }
  return l;
}

void rotate(int n, int m, bool flag) {
  int N = max(n, m);
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      tmp[i][j] = a[j][i];
  if (!flag) {
    for (int i = 1; i <= m; i++)
      for (int j = 1; j <= n/2; j++)
        swap(tmp[i][j], tmp[i][n-j+1]);
  }
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      a[i][j] = tmp[i][j];
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      pre[i][j] = max({a[i][j], pre[i-1][j], pre[i][j-1]});
  for (int i = 1; i <= N+1; i++) {
    for (int j = 1; j <= N+1; j++) {
      suf_mmin[i][j] = INF;
      suf_mmax[i][j] = 0;
    }
  }
  for (int i = m; i >= 1; i--) {
    for (int j = n; j >= 1; j--) {
      suf_mmin[i][j] = min({a[i][j], suf_mmin[i+1][j], suf_mmin[i][j+1]});
      suf_mmax[i][j] = max({a[i][j], suf_mmax[i+1][j], suf_mmax[i][j+1]});
    }
  }
  return;
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      cout << a[i][j] << " \n"[j==N];
  cout << "\n";
}

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  mmin = INF;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      mmin = min(mmin, a[i][j]);
    }
  }
  ans = INF;
  rotate(n, m, true);
  ans = min(ans, cal(m, n));
  rotate(m, n, false);
  ans = min(ans, cal(n, m));
  rotate(n, m, false);
  ans = min(ans, cal(m, n));
  rotate(m, n, false);
  ans = min(ans, cal(n, m));
  cout << ans << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

joioi.cpp: In function 'int cal(int, int)':
joioi.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     mid = l + r >> 1;
      |           ~~^~~

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