Submission #537797

#	Time	Username	Problem	Language	Result	Execution time	Memory
537797		truc12a2cvp	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2650 ms	31916 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> II;
const int N = 2e3 + 5, logN = 20;
const int MOD = 1e9 + 7;
const ll INF = 1e9;

int h, w, a[N][N], tmp[N][N], Min = INF, Max = 0;

void turn90(void){
       for(int i = 1; i <= h; i ++)
              for(int j = 1; j <= w; j ++) tmp[j][h - i + 1] = a[i][j];
       swap(h, w);
       for(int i = 1; i <= h; i ++) for(int j = 1; j <= w; j ++) a[i][j] = tmp[i][j];
}

bool check(int mid){
       int pref = INF;
       for(int i = 1; i <= h; i ++){
              int len = 0;
              while(len + 1 <= w && a[i][len + 1] - Min <= mid) len ++;
              pref = min(pref, len);
              for(int j = pref + 1; j <= w; j ++) if(Max - a[i][j] > mid) return false;
       }
       return true;
}

bool ok(int mid){
       for(int i = 0; i < 4; i ++){
              if(check(mid)) return true;
              turn90();
       }
       return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> h >> w;
    for(int i = 1; i <= h; i ++) for(int j = 1; j <= w; j ++) cin >> a[i][j], Min = min(Min, a[i][j]), Max = max(Max, a[i][j]);
    int ans = Max - Min, l = 0, r = ans - 1;
    while(l <= r){
       int mid = l + r >> 1;
       if(ok(mid)) ans = mid, r = mid - 1;
       else l = mid + 1;
    }
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:44:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |        int mid = l + r >> 1;
      |                  ~~^~~

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