Submission #549532

#	Time	Username	Problem	Language	Result	Execution time	Memory
549532		krit3379	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2894 ms	71060 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
#define N 2005


int a[N][N],b[N][N],ans=2e9;

bool valid(int n,int m,int val,int &ans){
    int i,j,mi[2],ma[2];
    bitset<N> dp[N];
    mi[0]=mi[1]=1e9;
    ma[0]=ma[1]=0;
    for(i=0;i<=m;i++)dp[n+1][i]=true;
    for(i=0;i<=n;i++)dp[i]=1;
    for(i=n;i>0;i--)for(j=1;a[i][j]<=val&&dp[i+1][j]&&dp[i][j-1];j++)dp[i][j]=true;
    if(dp[1][m])return true;
    if(!dp[n][1])return false;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            mi[dp[i][j]]=min(mi[dp[i][j]],a[i][j]);
            ma[dp[i][j]]=max(ma[dp[i][j]],a[i][j]);
        }
    }
    ans=min(ans,max(ma[0]-mi[0],ma[1]-mi[1]));
    if(mi[1]>=mi[0])return false;
    return ma[1]-mi[1]>ma[0]-mi[0];
}

int sol(int n,int m){
    int l=0,r=1e9,mid,ans=1e9;
    while(l<=r){
        mid=(l+r)/2;
        if(valid(n,m,mid,ans))r=mid-1;
        else l=mid+1;
    }
    return ans;
}

int main(){
    int n,m,i,j,k,mi=2e9,ma=0;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]);
    ans=min(ans,sol(n,m));
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)b[i][j]=a[i][j];
    for(i=1;i<=m;i++)for(j=1;j<=n;j++)a[i][j]=b[n-j+1][i];
    ans=min(ans,sol(m,n));
    for(i=1;i<=m;i++)for(j=1;j<=n;j++)b[i][j]=a[i][j];
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)a[i][j]=b[m-j+1][i];
    ans=min(ans,sol(n,m));
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)b[i][j]=a[i][j];
    for(i=1;i<=m;i++)for(j=1;j<=n;j++)a[i][j]=b[n-j+1][i];
    ans=min(ans,sol(m,n));
    printf("%d",ans);
    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:40:17: warning: unused variable 'k' [-Wunused-variable]
   40 |     int n,m,i,j,k,mi=2e9,ma=0;
      |                 ^
joioi.cpp:40:19: warning: unused variable 'mi' [-Wunused-variable]
   40 |     int n,m,i,j,k,mi=2e9,ma=0;
      |                   ^~
joioi.cpp:40:26: warning: unused variable 'ma' [-Wunused-variable]
   40 |     int n,m,i,j,k,mi=2e9,ma=0;
      |                          ^~
joioi.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
joioi.cpp:42:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]);
      |                                       ~~~~~^~~~~~~~~~~~~~~

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