Submission #201421

#	Time	Username	Problem	Language	Result	Execution time	Memory
201421		quocnguyen1012	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	724 ms	55008 KiB

joioi

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 2005;

int a[maxn][maxn], N, M;
int mi = 1e9, ma = 0;

bool check(int val){
    int L = 1 ,  R = M;
    bool ok = 1  , ok1 = 1;
    for(int i = 1 ; i <= N ; ++i){
        int l = M , r = 1;
        for( ; l >= 1 ; --l){
            if(a[i][l] - mi > val)break;
        }
        for( ; r <= M ; ++r){
            if(ma - a[i][r] > val)break;
        }
        --r;++l;
        R = min(R , r);
        if(R < l - 1)ok = 0;
        L = max(L , l);
        if(r + 1 < L)ok1 = 0;
        if(!ok && !ok1)break;
//        cout << l << " " << r << endl;
    }
//    cout << endl;
    if(ok || ok1)return 1;
    ok = 1 , ok1 = 1;
    L = 1;R = M;
    for(int i = 1 ; i <= N ; ++i){
        int l = M , r = 1;
        for( ; l >= 1 ; --l){
            if(ma - a[i][l] > val)break;
        }
        for( ; r <= M ; ++r){
            if(a[i][r] - mi > val)break;
        }
        --r;++l;
        R = min(R , r);
        if(R < l - 1)ok = 0;
        L = max(L , l);
        if(r + 1 < L)ok1 = 0;
        if(!ok && !ok1)break;
//        cout << l << " " << r << endl;
    }
    if(ok || ok1)return 1;
    return 0;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> M;
  for (int i = 1; i <= N; ++i){
    for (int j = 1; j <= M; ++j){
      cin >> a[i][j];
      mi = min(mi, a[i][j]);
      ma = max(ma, a[i][j]);
    }
  }
  int l = 0, r = ma - mi, mid;
  while (l <= r){
    mid = (l + r) / 2;
    if (!check(mid)) l = mid + 1;
    else r = mid - 1;
  }
  cout << min(l, ma - mi);
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:63:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
joioi.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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