Submission #747569

#	Time	Username	Problem	Language	Result	Execution time	Memory
747569		Andrei_ierdnA	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1077 ms	102080 KiB

joioi

#include <iostream>
#include <iomanip>

using namespace std;

#define INF 1000000001

int n, m, i, j, a[2010][2010], ao[2010][2010], av[2010][2010], ac[2010][2010];
int mini = INF, maxi = 0, st, dr, mij, sol;

bool testDiff (int x, int (&a)[2010][2010])
{
    int prevh = n;
    for (j = 1; j <= m; j++) {
        for (i = 1; i <= prevh; i++) {
            if (a[i][j] > mini+x)
                break;
        }
        prevh = i-1;
        for (; i <= n; i++) {
            if (a[i][j] < maxi-x)
                return false;
        }
    }
    return true;
}

bool testAllDiff (int x)
{
    return (testDiff(x, a) || testDiff(x, ao) || testDiff(x, av) || testDiff(x, ac));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            cin >> a[i][j];
            mini = min(mini, a[i][j]);
            maxi = max(maxi, a[i][j]);
            ao[n-i+1][j] = a[i][j];
            av[i][m-j+1] = a[i][j];
            ac[n-i+1][m-j+1] = a[i][j];
        }
    }
    st = 0;
    dr = maxi-mini;
    sol = -1;
    while (st <= dr) {
        mij = (st+dr) / 2;
        bool ok = testAllDiff(mij);
        if (ok) {
            sol = mij;
            dr = mij-1;
        }
        else {
            st = mij+1;
        }
    }
    cout << sol;
    return 0;
}

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