Submission #550415

#	Time	Username	Problem	Language	Result	Execution time	Memory
550415		ToroTN	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	24 ms	16076 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
int n,m,a[2005][2005],b[2005][2005],st,md,ed,num,dp[2005][2005];
int cnt,ans=1e9;
vector<int> v;
vector<pair<int,int> > p;
void rotate()
{
    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];
        }
    }
}
int find_ans()
{
    st=0;
    ed=p.size()-1;
    while(ed>=st)
    {
        md=(st+ed)/2;
        if(md==p.size()-1)
        {
            num=0;
        }else
        {
            num=p[md+1].second;
        }
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(j+1<=m)
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j]+(abs(a[i][j]-a[i][j+1])>p[md].first));
                }else
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j]);
                }
                if(i+1<=n)
                {
                    dp[i][j]=max(dp[i][j],dp[i][j-1]+(abs(a[i][j]-a[i+1][j])>p[md].first));
                }else
                {
                    dp[i][j]=max(dp[i][j],dp[i][j-1]);
                }
            }
        }
        if(dp[n][m]==num)
        {
            ed=md-1;
        }else
        {
            st=md+1;
        }
    }
    //printf("%d %d %d\n",st,md,ed);
    return p[st].first;
}
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++)
    {
        if(i==0)
        {
            cnt=1;
            continue;
        }
        if(v[i]==v[i-1])
        {
            ++cnt;
        }else
        {
            p.push_back({v[i-1],cnt});
            cnt=1;
        }
    }
    p.push_back({v[v.size()-1],cnt});
    for(int i=p.size()-2;i>=0;i--)
    {
        p[i].second=p[i].second+p[i+1].second;
    }
    ans=min(ans,find_ans());
    rotate();
    ans=min(ans,find_ans());
    rotate();
    ans=min(ans,find_ans());
    rotate();
    ans=min(ans,find_ans());
    printf("%d\n",ans);
}

Compilation message (stderr)

joioi.cpp: In function 'int find_ans()':
joioi.cpp:32:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if(md==p.size()-1)
      |            ~~^~~~~~~~~~~~
joioi.cpp: In function 'int main()':
joioi.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
joioi.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
joioi.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |             scanf("%d",&a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~

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