oj.uz

Submission #970220

# Submission time Handle Problem Language Result Execution time Memory
970220 2024-04-26T08:26:35 Z 12345678 The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 2396 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -