Submission #206178

#	Time	Username	Problem	Language	Result	Execution time	Memory
206178		stefdasca	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1210 ms	43384 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
int n, m, a[2002][2002], mxA[2002], mnA[2002], mxB[2002], mnB[2002], mx, mn;
bool okA[2002][2002], okB[2002][2002];
bool chk(int vdif)
{
    for(int i = 1; i <= m; ++i)
    {
        mnA[i] = mnB[i] = n+1;
        mxA[i] = mxB[i] = 0;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            if(a[i][j] - mn <= vdif)
                okA[i][j] = 1;
            else
                okA[i][j] = 0;
            if(mx - a[i][j] <= vdif)
                okB[i][j] = 1;
            else
                okB[i][j] = 0;
            if(!okA[i][j] && !okB[i][j])
                return 0;
            if(okA[i][j] && !okB[i][j])
            {
                mxA[j] = max(mxA[j], i);
                mnA[j] = min(mnA[j], i);
            }
            if(okB[i][j] && !okA[i][j])
            {
                mxB[j] = max(mxB[j], i);
                mnB[j] = min(mnB[j], i);
            }
        }
   // cout << vdif << '\n';
    bool ok = 1;
    bool ok2 = 1;
    int mxxA = 0, mxxB = 0;
    for(int i = 1; i <= m; ++i)
    {
        /*
        cout << mxA[i] << " " << mnA[i] << " " << mxB[i] << " " << mnB[i] << '\n';
        cout << mxxA << " " << mxxB << '\n';
        cout << ok << " " << ok2 << '\n';
        */
        if(mxA[i] > mnB[i])
            ok = 0;
        if(mxB[i] > mnA[i])
            ok2 = 0;
        if(mnB[i] - 1 < mxxA)
            ok = 0;
        if(mnA[i] - 1 < mxxB)
            ok2 = 0;
        mxxA = max(mxxA, mxA[i]);
        mxxB = max(mxxB, mxB[i]);
    }
    if(ok)
        return 1;
    if(ok2)
        return 1;
    ok = 1;
    ok2 = 1;
    mxxA = n+1, mxxB = n+1;
    for(int i = 1; i <= m; ++i)
    {
        /*
        cout << mxA[i] << " " << mnA[i] << " " << mxB[i] << " " << mnB[i] << '\n';
        cout << mxxA << " " << mxxB << '\n';
        cout << ok << " " << ok2 << '\n';
        */
        if(mxA[i] > mnB[i])
            ok = 0;
        if(mxB[i] > mnA[i])
            ok2 = 0;
        if(mxA[i] > mxxA)
            ok = 0;
        if(mxB[i] > mxxB)
            ok2 = 0;
        mxxA = min(mxxA, mnB[i] - 1);
        mxxB = min(mxxB, mnA[i] - 1);
    }
    if(ok)
        return 1;
    if(ok2)
        return 1;
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    mn = 1000000001;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            cin >> a[i][j];
            mx = max(mx, a[i][j]);
            mn = min(mn, a[i][j]);
        }
    int st = 0;
    int dr = mx - mn;
    int ans = dr;
    while(st <= dr)
    {
        int mid = (st + dr) / 2;
        if(chk(mid))
            ans = mid, dr = mid - 1;
        else
            st = mid + 1;
    }
    cout << ans << '\n';
    return 0;
}

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