Submission #970220

#	Time	Username	Problem	Language	Result	Execution time	Memory
970220		12345678	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	1 ms	2396 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+5;

int h, w, mp[nx][nx], dp[nx], v[nx][nx], mn, mx, l, r, ans;

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];
    for (int i=1; i<=h; i++)
    {
        mn=mx=mp[i][w];
        for (int j=w; j>=1; j--) mn=min(mn, mp[i][j]), mx=max(mx, mp[i][j]), v[i][j]=mx-mn;
    }
    int l=0, r=1e9;
    dp[0]=dp[h+1]=1e9;
    while (l<r)
    {
        int md=(l+r)/2, f=0;
        for (int i=1; i<=h; i++)
        {
            mn=mx=mp[i][1];
            dp[i]=1;
            for (int j=2; j<=w; j++)
            {
                mn=min(mn, mp[i][j]);
                mx=max(mx, mp[i][j]);
                if (mx-mn<=md) dp[i]=j;
                else break;
            }
            dp[i]=min(dp[i], dp[i-1]);
            if (v[i][dp[i]+1]>md) f=1;
        }
        if (f) l=md+1;
        else r=md;
    }
    ans=l;
    l=0, r=1e9;
    while (l<r)
    {
        int md=(l+r)/2, f=0;
        for (int i=h; i>=1; i--)
        {
            mn=mx=mp[i][1];
            dp[i]=1;
            for (int j=2; j<=w; j++)
            {
                mn=min(mn, mp[i][j]);
                mx=max(mx, mp[i][j]);
                if (mx-mn<=md) dp[i]=j;
                else break;
            }
            dp[i]=min(dp[i], dp[i+1]);
            if (v[i][dp[i]+1]>md) f=1;
        }
        if (f) l=md+1;
        else r=md;
    }
    //cout<<"debug "<<ans<<' '<<l<<'\n';
    cout<<min(ans, l);
}

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