Submission #757104

#	Time	Username	Problem	Language	Result	Execution time	Memory
757104		gun_gan	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	704 ms	17180 KiB

joioi

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

const int MX = 2005;

int a[MX][MX];
int H, W, mn = 1e9, mx = 0;

bool can(int x) {
      // cek atas kanan
      int lst = W - 1;
      bool ok = 1;
      for(int i = 0; i < H; i++) {
            for(int j = 0; j <= lst; j++) {
                  if(a[i][j] > mn + x) {
                        lst = j - 1;
                        break;
                  }
            }

            for(int j = lst + 1; j < W; j++) {
                  ok &= a[i][j] >= mx - x;
            }
      }

      if(ok) return 1;
      ok = 1;
      lst = 0;

      for(int i = 0; i < H; i++) {
            for(int j = W - 1; j >= lst; j--) {
                  if(a[i][j] > mn + x) {
                        lst = j + 1;
                        break;
                  }
            }

            for(int j = 0; j < lst; j++) {
                  ok &= a[i][j] >= mx - x;
            }
      }

      if(ok) return 1;

      ok = 1;
      lst = W - 1;
      for(int i = H - 1; i >= 0; i--) {
            for(int j = 0; j <= lst; j++) {
                  if(a[i][j] > mn + x) {
                        lst = j - 1;
                        break;     
                  }
            }

            for(int j = lst + 1; j < W; j++) {
                  ok &= a[i][j] >= mx - x;
            }
      }

      if(ok) return 1;

      ok = 1;
      lst = 0;
      for(int i = H - 1; i >= 0; i--) {
            for(int j = W - 1; j >= lst; j--) {
                  if(a[i][j] > mn + x) {
                        lst = j + 1;
                        break;
                  }
            }

            for(int j = 0; j < lst; j++) {
                  ok &= a[i][j] >= mx - x;
            }
      }
      
      return ok;
}

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0); 

      cin >> H >> W;
      for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) {
                  cin >> a[i][j];
                  mn = min(mn, a[i][j]);
                  mx = max(mx, a[i][j]);
            }
      }

      int l = 0, r = 1e9, ans = 0;
      while(l <= r) {
            int mid = (l + r) >> 1;
            if(can(mid)) {
                  r = mid - 1, ans = mid;
            } else {
                  l = mid + 1;
            }
      }
      
      cout << ans << '\n';
}

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