Submission #87903

#	Time	Username	Problem	Language	Result	Execution time	Memory
87903		tieunhi	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2285 ms	53992 KiB

joioi

#include <bits/stdc++.h>
#define pii pair<ll, ll>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define N 2003
#define LN 19
#define maxc 1000000007

using namespace std;

int n, m, a[N][N], amin, amax, pos[N];
bool b[N][N];
void revRow()
{
    FOR(i, 1, n)
        FOR(j, 1, m/2)
            swap(a[i][j], a[i][m-j+1]);
}
void revCol()
{
    FOR(j, 1, m)
        FOR(i, 1, n/2)
            swap(a[i][j], a[n-i+1][j]);
}
bool ok(int diff)
{
    FOR(i, 1, n)
        FOR(j, 1, m)
            b[i][j] = (a[i][j] >= (amax - diff));
    pos[0] = m;
    FOR(i, 1, n)
    {
        pos[i] = pos[i-1];
        FOR(j, 1, pos[i-1])
            if (b[i][j] == 0) {pos[i] = j-1; break;}
    }
    int mx = 0, mn = maxc;
    if (pos[n] == m) return 1;
    FOR(i, 1, n)
        FOR(j, pos[i]+1, m)
        {
            mx = max(mx, a[i][j]);
            mn = min(mn, a[i][j]);
        }
    if (abs(mx - mn) <= diff) return 1;
    return 0;
}
bool check(int diff)
{

    if (ok(diff)) return 1;
    revRow();
    if (ok(diff)) return 1;
    revCol();
    if (ok(diff)) return 1;
    revRow();
    if (ok(diff)) return 1;
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> m;
    amin = maxc, amax = 0;
    FOR(i, 1, n)
        FOR(j, 1, m)
        {
            cin >> a[i][j];
            amax = max(amax, a[i][j]);
            amin = min(amin, a[i][j]);
        }
    int l = 0, r = amax - amin + 1;
    while (r - l > 1)
    {
        int mid = (r + l)/2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    cout <<r;
}

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