oj.uz

Submission #132815

# Submission time Handle Problem Language Result Execution time Memory
132815 2019-07-19T16:15:33 Z nvmdava The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 2 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;

int h, w;
int a[2005][2005];

bool check(int v){
   int l = 0, r = w;
   int ok = 0;
   for(int i = 1; i <= h; i++){
      int L = 0, R = w;
      int t = a[i][1];
      for(int j = 2; j <= w; j++){
         if(a[i][j] > t + v){
            R = min(R, j - 1);
            break;
         }
         t = min(t, a[i][j]);
      }
      t = a[i][1];
      for(int j = 2; j <= w; j++){
         if(a[i][j] < t - v){
            R = min(R, j - 1);
            break;
         }
         t = max(t, a[i][j]);
      }
      t = a[i][w];
      for(int j = w - 1; j > 0; j--){
         if(a[i][j] < t - v){
            L = max(L, j);
            break;
         }
         t = max(t, a[i][j]);
      }
      t = a[i][w];
      for(int j = w - 1; j > 0; j--){
         if(a[i][j] > t + v){
            L = max(L, j);
            break;
         }
         t = min(t, a[i][j]);
      }
      if(l > R) ok |= 1;
      if(r < L) ok |= 2;
      if(L > R) return 0;
      if(ok == 3) return 0;
      r = min(r, R);
      l = max(l, L);
   }
   return 1;
}

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

   cin>>h>>w;
   for(int i = 1; i <= h; i++)
      for(int j = 1; j <= w; j++)
         cin>>a[i][j];

   int l = 0, r = 1000000000;
   while(l != r){
      int m = (l + r) >> 1;
      if(check(m)) r = m;
      else l = m + 1;
   }
   cout<<l;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -