Submission #43700

#	Time	Username	Problem	Language	Result	Execution time	Memory
43700		dqhungdl	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1429 ms	262144 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

int m,n,minn=1e9,maxn=0,a[2005][2005];
bool Free[2005][2005];

int Dist()
{
    int min1=1e9,max1=0,min2=1e9,max2=0;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(Free[i][j]==false)
            {
                min1=min(min1,a[i][j]);
                max1=max(max1,a[i][j]);
            }
            else
            {
                min2=min(min2,a[i][j]);
                max2=max(max2,a[i][j]);
            }
    return max(max1-min1,max2-min2);
}

bool CheckMin(int lim)
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            Free[i][j]=false;
    for(int j=1;j<=n;j++)
        Free[0][j]=true;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]<=minn+lim&&Free[i-1][j]==true)
                Free[i][j]=true;
            else
                break;
    if(Dist()<=lim)
        return true;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            Free[i][j]=false;
    for(int j=1;j<=n;j++)
        Free[m+1][j]=true;
    for(int i=m;i>=1;i--)
        for(int j=1;j<=n;j++)
            if(a[i][j]<=minn+lim&&Free[i+1][j]==true)
                Free[i][j]=true;
            else
                break;
    if(Dist()<=lim)
        return true;
    return false;
}

bool CheckMax(int lim)
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            Free[i][j]=false;
    for(int j=1;j<=n;j++)
        Free[0][j]=true;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]>=maxn-lim&&Free[i-1][j]==true)
                Free[i][j]=true;
            else
                break;
    if(Dist()<=lim)
        return true;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            Free[i][j]=false;
    for(int j=1;j<=n;j++)
        Free[m+1][j]=true;
    for(int i=m;i>=1;i--)
        for(int j=1;j<=n;j++)
            if(a[i][j]>=maxn-lim&&Free[i+1][j]==true)
                Free[i][j]=true;
            else
                break;
    if(Dist()<=lim)
        return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            minn=min(minn,a[i][j]);
            maxn=max(maxn,a[i][j]);
        }
    int res,l=0,r=1e9;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(CheckMin(mid)==true||CheckMax(mid)==true)
        {
            res=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout<<res;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:111:14: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<res;
              ^

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