Submission #592754

#	Time	Username	Problem	Language	Result	Execution time	Memory
592754		hail	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	443 ms	16060 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

int h{};
int w{};
int max_alt{0};
int min_alt(1e9);

bool check_kingdom(int x, int country[2000][2000])
{
    int border{w};
    bool valid;
    bool element_present;
    //min left top
    if(country[0][0]-min_alt<=x)
    {
        valid=true;
        element_present=false;
        for(int i=0; i<h; i++)
        {
            for(int j=0; j<w; j++)
            {
                if(j<border)
                {
                    if(country[i][j]==min_alt) element_present=true;
                    if(country[i][j]-min_alt>x) {border=j; j--;}
                }
                else
                {
                    if(max_alt-country[i][j]>x)
                    {
                        valid=false;
                        break;
                    }
                }
                if(border==0 && (not element_present))
                {
                    valid=false;
                    break;
                }
            }
            if(not valid) break;
        }
        if(valid) return true;
    }
    //min left bottom
    border=w;
    if(country[h-1][0]-min_alt<=x)
    {
        element_present=false;
        valid=true;
        for(int i=h-1; i>=0; i--)
        {
            for(int j=0; j<w; j++)
            {
                if(j<border)
                {
                    if(country[i][j]==min_alt) element_present=true;
                    if(country[i][j]-min_alt>x) {border=j; j--;}
                }
                else
                {
                    if(max_alt-country[i][j]>x)
                    {
                        valid=false;
                        break;
                    }
                }
                if(border==0 && (not element_present))
                {
                    valid=false;
                    break;
                }
            }
            if(not valid) break;
        }
        if(valid) return true;
    }
    //max left top
    border=w;
    if(max_alt-country[0][0]<=x)
    {
        valid=true;
        element_present=false;
        for(int i=0; i<h; i++)
        {
            for(int j=0; j<w; j++)
            {
                if(j<border)
                {
                    if(country[i][j]==max_alt) element_present=true;
                    if(max_alt-country[i][j]>x) {border=j; j--;}
                }
                else
                {
                    if(country[i][j]-min_alt>x)
                    {
                        valid=false;
                        break;
                    }
                }
                if(border==0 && (not element_present))
                {
                    valid=false;
                    break;
                }
            }
            if(not valid) break;
        }
        if(valid) return true;
    }
    //max left bottom
    border=w;
    if(max_alt-country[h-1][0]<=x)
    {
        element_present=false;
        valid=true;
        for(int i=h-1; i>=0; i--)
        {
            for(int j=0; j<w; j++)
            {
                if(j<border)
                {
                    if(country[i][j]==max_alt) element_present=true;
                    if(max_alt-country[i][j]>x) {border=j; j--;}
                }
                else
                {
                    if(country[i][j]-min_alt>x)
                    {
                        valid=false;
                        break;
                    }
                }
                if(border==0 && (not element_present))
                {
                    valid=false;
                    break;
                }
            }
            if(not valid) break;
        }
        if(valid) return true;
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>h>>w;
    int country[2000][2000];


    for(int i=0; i<h; i++)
    {
        for(int j=0; j<w; j++)
        {
            cin>>country[i][j];
            max_alt=max(max_alt, country[i][j]);
            min_alt=min(min_alt, country[i][j]);
        }
    }

    int high=max_alt-min_alt;
    int low=-1;

    int mid;

    while(high-low>1)
    {
        mid=(high+low)/2;
        if(check_kingdom(mid, country)) high=mid;
        else low=mid;
    }

    cout<<high;

    return 0;

}

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