oj.uz

Submission #82748

# Submission time Handle Problem Language Result Execution time Memory
82748 2018-11-01T14:54:17 Z Bodo171 The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 2 ms 508 KB 
#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;
bool check(int val)
{
    int st=1,dr=m,l,r;
    bool 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/2;i++)
        for(j=1;j<=m;j++)
            swap(a[i][j],a[n-i+1][j]);
    ans=min(solve(),ans);
    cout<<ans;
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 508 KB Output isn't correct
3 Halted 0 ms 0 KB -