oj.uz

Submission #550401

# Submission time Handle Problem Language Result Execution time Memory
550401 2022-04-18T04:23:04 Z ToroTN The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,a[2005][2005],b[2005][2005],st,md,ed,ans1,ans2,num,dp[2005][2005];
vector<int> v;
int find_ans()
{
    st=1;
    ed=1e9;
    while(ed>=st)
    {
        md=(st+ed)/2;
        //printf("group=%d %d %d\n",st,md,ed);
        num=upper_bound(v.begin(),v.end(),-md)-v.begin();
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dp[i][j]=-1e9;
        dp[1][1]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(i-1>0)dp[i][j]=max(dp[i][j],dp[i-1][j]+(abs(a[i-1][j]-a[i][j])>=md));
                if(j-1>0)dp[i][j]=max(dp[i][j],dp[i][j-1]+(abs(a[i][j-1]-a[i][j])>=md));
            }
        }
        /*for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                printf("%d ",dp[i][j]);
            }
            printf("\n");
        }
        printf("%d %d\n\n",dp[n][m],num);*/
        if(dp[n][m]==num)
        {
            ed=md-1;
        }else
        {
            st=md+1;
        }
    }
    //printf("%d %d %d\n",st,md,ed);
    num=-v[upper_bound(v.begin(),v.end(),-st)-v.begin()];
    return num;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            v.push_back(-abs(a[i][j]-a[i+1][j]));
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<m;j++)
        {
            v.push_back(-abs(a[i][j]-a[i][j+1]));
        }
    }
    sort(v.begin(),v.end());
    /*for(int i=0;i<v.size();i++)
    {
        printf("%d ",v[i]);
    }
    printf("\n");*/
    ans1=find_ans();
    for(int i=1;i<=m;i++)
    {
        for(int j=n;j>=1;j--)
        {
            b[i][n-j+1]=a[j][i];
        }
    }
    swap(n,m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]=b[i][j];
        }
    }
    ans2=find_ans();
    printf("%d\n",min(ans1,ans2));
}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
joioi.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |             scanf("%d",&a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -