oj.uz

답안 #321663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321663 2020-11-13T02:44:43 Z casperwang The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 640 KB 
#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) {
  int N = max(n, m);
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      tmp[i][j] = a[N-j+1][i];
  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]});
    }
  }
}

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);
  ans = min(ans, cal(m, n));
  rotate(m, n);
  ans = min(ans, cal(n, m));
  rotate(n, m);
  ans = min(ans, cal(m, n));
  rotate(m, n);
  ans = min(ans, cal(n, m));
  cout << ans << "\n";
}

Compilation message

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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -