Submission #255240

#	Time	Username	Problem	Language	Result	Execution time	Memory
255240		test2	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1303 ms	86336 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

const int N = 2002;

int n, m;
int a[N][N];
int ans;
int mn = 1e9 + 7, mx;

int ok1[N][N], ok2[N][N];

int mnA[N], mxA[N];
int mnB[N], mxB[N];

bool check(int val)
{
        memset(ok1, 0, sizeof ok1);
        memset(ok2, 0, sizeof ok2);
        for (int i = 0; i < m; i++)
        {
                mnA[i] = n;
                mnB[i] = n;
                mxA[i] = -1;
                mxB[i] = -1;
        }
        
        for (int i = 0; i < n; i++)
        {
                for (int j = 0; j < m; j++)
                {
                        if (a[i][j] - mn <= val)
                                ok1[i][j] = 1;
                        else
                                ok1[i][j] = 0;

                        if (mx - a[i][j] <= val)
                                ok2[i][j] = 1;
                        else
                                ok2[i][j] = 0;

                        if (!ok1[i][j] && !ok2[i][j])
                                return 0;

                        if (ok1[i][j] && !ok2[i][j])
                        {
                                mnA[j] = min(mnA[j], i);
                                mxA[j] = max(mxA[j], i);
                        }
                        if (!ok1[i][j] && ok2[i][j])
                        {
                                mnB[j] = min(mnB[j], i);
                                mxB[j] = max(mxB[j], i);
                        }
                }
        }


        //increasing starting from row 0
        bool k1 = 1, k2 = 1;
        int mnca = -1, mncb = -1;
        for (int i = 0; i < m; i++)
        {
                mnca = max(mnca, mxA[i]);
                mncb = max(mncb, mxB[i]);

                if (mnca >= mnB[i])
                        k1 = 0;
                if (mncb >= mnA[i])
                        k2 = 0;
        }

        if (k1 || k2)
                return 1;

        for (int i = 0; i < n; i++)
        {
                for (int j = 0; j < m; j++)
                {
                        //   int an = ok1[i][j] + ok2[i][j];
                        // cout << an << " ";
                }
                //  cout << "\n";
        }

        //decreasing starting from row 0
        k1 = 1, k2 = 1;
        mnca = -1, mncb = -1;

        for (int i = m - 1; i >= 0; i--)
        {
                mnca = max(mnca, mxA[i]);
                mncb = max(mncb, mxB[i]);

                if (mnca >= mnB[i])
                        k1 = 0;
                if (mncb >= mnA[i])
                        k2 = 0;
        }

        if (k1 || k2)
                return 1;

        // increasing starting at row n

        k1 = 1, k2 = 1;
        int mxca = n, mxcb = n;

        for (int i = 0; i < m; i++)
        {
                mnca = min(mnca, mnA[i]);
                mncb = min(mncb, mnB[i]);

                if (mxca >= mxB[i])
                        k1 = 0;
                if (mxcb >= mxA[i])
                        k2 = 0;
        }
        if (k1 || k2)
                return 1;

        //decreasing starting at row n

        k1 = 1, k2 = 1;
        mxca = n, mxcb = n;

        for (int i = m - 1; i >= 0; i--)
        {
                mnca = min(mnca, mnA[i]);
                mncb = min(mncb, mnB[i]);

                if (mxca >= mxB[i])
                        k1 = 0;
                if (mxcb >= mxA[i])
                        k2 = 0;
        }
        if (k1 | k2)
                return 1;

        return (k1 | k2);
}

int main()
{

        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);

        cin >> n >> m;
        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]);
                }
        }

        int lo = 0, hi = mx - mn;

        for (; lo <= hi;)
        {
                int mid = (lo + hi) >> 1;

                if (check(mid))
                        ans = mid, hi = mid - 1;
                else
                        lo = mid + 1;
        }

        cout << ans;

        return 0;
}

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