Submission #978195

#	Time	Username	Problem	Language	Result	Execution time	Memory
978195		12345678	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	362 ms	117692 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+5;

int h, w, mp[nx][nx], l, r, dplmx[nx][nx], dprmx[nx][nx], dplmn[nx][nx], dprmn[nx][nx], mn=INT_MAX;

bool solve1(int x)
{
    int pts=w, cmn=INT_MAX, cmx=0;
    for (int i=1; i<=h; i++)
    {
        while (dplmx[i][pts]>mn+x) pts--;
        cmn=min(cmn, dprmn[i][pts+1]);
        cmx=max(cmx, dprmx[i][pts+1]);
    }
    return (cmx-cmn)<=x;
}

bool solve2(int x)
{
    int pts=w, cmn=INT_MAX, cmx=0;
    for (int i=h; i>=1; i--)
    {
        while (dplmx[i][pts]>mn+x) pts--;
        cmn=min(cmn, dprmn[i][pts+1]);
        cmx=max(cmx, dprmx[i][pts+1]);
    }
    return (cmx-cmn)<=x;
}

bool solve3(int x)
{
    int pts=1, cmn=INT_MAX, cmx=0;
    for (int i=1; i<=h; i++)
    {
        while (dprmx[i][pts]>mn+x) pts++;
        cmn=min(cmn, dplmn[i][pts-1]);
        cmx=max(cmx, dplmx[i][pts-1]);
    }
    return (cmx-cmn)<=x;
}

bool solve4(int x)
{
    int pts=1, cmn=INT_MAX, cmx=0;
    for (int i=h; i>=1; i--)
    {
        while (dprmx[i][pts]>mn+x) pts++;
        cmn=min(cmn, dplmn[i][pts-1]);
        cmx=max(cmx, dplmx[i][pts-1]);
    }
    return (cmx-cmn)<=x;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>h>>w;
    for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) cin>>mp[i][j], mn=min(mn, mp[i][j]);
    for (int i=1; i<=h; i++) dplmn[i][0]=dprmn[i][w+1]=INT_MAX;
    for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) dplmx[i][j]=max(dplmx[i][j-1], mp[i][j]), dplmn[i][j]=min(dplmn[i][j-1], mp[i][j]);
    for (int i=1; i<=h; i++) for (int j=w; j>=1; j--) dprmx[i][j]=max(dprmx[i][j+1], mp[i][j]), dprmn[i][j]=min(dprmn[i][j+1], mp[i][j]);
    l=0, r=1e9;
    while (l<r)
    {
        int md=(l+r)/2;
        if (solve1(md)||solve2(md)||solve3(md)||solve4(md)) r=md;
        else l=md+1;
    }
    cout<<l;
}

/*
3 3
1 1 1
10 10 10
1 1
*/

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