Submission #82760

#	Time	Username	Problem	Language	Result	Execution time	Memory
82760		Bodo171	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	975 ms	20504 KiB

joioi

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=2005;
int a[nmax][nmax];
int mn,mx,ans,n,m,i,j;
int st,dr,l,r;
bool cresc,desc;
bool check(int val)
{
    st=0,dr=m;
    cresc=1,desc=1;
    for(i=1;i<=n&&(cresc||desc);i++)
    {
        r=1;l=m;
        while(a[i][r]-mn<=val&&r<=m)
            r++;
        r--;
        while(mx-a[i][l]<=val&&l>0)
            l--;
        st=max(st,l);dr=min(r,dr);
        if(st>r)
            cresc=0;
        if(dr<l)
            desc=0;
    }
    return (cresc||desc);
}
int solve()
{
    int ret=(1<<30)-1;
    for(int p=29;p>=0;p--)
        if(check(ret-(1<<p)))
           ret-=(1<<p);
    return ret;
}
int main()
{
   // freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;mn=(1<<30);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
    {
        cin>>a[i][j];
        mn=min(a[i][j],mn);
        mx=max(a[i][j],mx);
    }
    ans=mx-mn;
    ans=min(solve(),ans);
    for(i=1;i<=n;i++)
        for(j=1;j<=m/2;j++)
            swap(a[i][j],a[i][m-j+1]);
    ans=min(solve(),ans);
    cout<<ans;
    return 0;
}

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