Submission #132815

#	Time	Username	Problem	Language	Result	Execution time	Memory
132815		nvmdava	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	2 ms	504 KiB

joioi

#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
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40