Submission #152644

#	Time	Username	Problem	Language	Result	Execution time	Memory
152644		karma	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1229 ms	47532 KiB

joioi

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define pb      emplace_back
#define mp      make_pair
#define fi      first
#define se      second
#define ll      long long

using namespace std;

const int N = int(2e3) + 3;
const int inf = int(1e9) + 3;

int n, m, a[N][N], Max[N][N], Min[N][N];
int low, mid, high, lim, mn, mx, res, Mx, Mn, h;
bool divided;

bool Check() {
     lim = mn + mid;
     if(a[0][0] > lim && a[0][m - 1] > lim) return 0;
     Mx = 0, Mn = inf, h = n;
     for(int j = 0; j < m; ++j) {
         divided = 0;
         for(int i = 0; i < n; ++i) {
            if(a[i][j] <= lim && i < h && !divided) continue;
             if(!divided) {
                divided = 1, h = min(h, i);
                Mx = max(Mx, Max[i][j]);
                Mn = min(Mn, Min[i][j]);
                break;
            }
         }
     }
     if(Mx - Mn <= mid) return 1;
     h = n, Mx = 0, Mn = inf;
     for(int j = m - 1; j >= 0; --j) {
         divided = 0;
         for(int i = 0; i < n; ++i) {
            if(a[i][j] <= lim && i < h && !divided) continue;
            if(!divided) {
                divided = 1, h = min(h, i);
                Mx = max(Mx, Max[i][j]);
                Mn = min(Mn, Min[i][j]);
                break;
            }
         }
     }
     return Mx - Mn <= mid;
}

void Solve() {
     for(int i = n - 1; i >= 0; --i) {
        for(int j = 0; j < m; ++j) {
            if(i + 1 < n) {
                Max[i][j] = max(Max[i + 1][j], a[i][j]);
                Min[i][j] = min(Min[i + 1][j], a[i][j]);
            } else Max[i][j] = Min[i][j] = a[i][j];
        }
     }
     mid = res - 1;
     if(!Check()) return;
     low = 0, high = res - 1;
     while(low <= high) {
         mid = (low + high) >> 1;
         if(Check()) high = mid - 1;
         else low = mid + 1;
     }
     res = min(res, low);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> n >> m; mn = inf, mx = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
           cin >> a[i][j];
           mn = min(mn, a[i][j]);
           mx = max(mx, a[i][j]);
        }
    }
    res = mx - mn;
    Solve();
    for(int j = 0; j < m; ++j) {
        for(int i = 0; n - 1 - i > i; ++i) {
            swap(a[i][j], a[n - 1 - i][j]);
        }
    }
    Solve();
    cout << res;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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