Submission #978817

#	Time	Username	Problem	Language	Result	Execution time	Memory
978817		sleepntsheep	The Kingdom of JOIOI (JOI17_joioi)	C11	100 / 100	1377 ms	117784 KiB

joioi

#include<stdio.h>

#define N 2000
#define M 2000

int max(int i,int j){return i<j?j:i;}
int min(int i,int j){return i>j?j:i;}

int n, m, a[N][M], b[N][M], c[N][M], d[N][M], x, ii, jj;

int ok_(int a[][M], int ii, int jj)
{
    static int down[M][N];
    for(int i=0;i<m;++i)
    {
        down[i][0]=a[0][i];
        for(int j=1;j<n;++j)
            down[i][j]=min(down[i][j-1],a[j][i]);
    }

    int high = a[ii][jj];

    static int sep[M];
    int ptr=n-1;
    for(int i=0;i<m;++i)
    {
        while(ptr>=0&&down[i][ptr]+x<high)--ptr;
        sep[i]=ptr+1;
        if(jj == i && sep[i] <= ii)
            return 0;
    }

    int ioi_high=-1,ioi_low=1e9;
    for(int i=0;i<m;++i)for(int j=sep[i];j<n;++j)
    {
        ioi_high=max(ioi_high,a[j][i]);
        ioi_low=min(ioi_low,a[j][i]);
        if(ioi_low+x<ioi_high)
            return 0;
    }
    return 1;
}

int ok(int x0)
{
    x = x0;
    return ok_(a, ii, jj) || ok_(b, n-1-ii, jj) || ok_(c, ii, m-1-jj) || ok_(d, n-1-ii, m-1-jj);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i)for(int j=0;j<m;++j)
    {
        scanf("%d",a[i]+j), b[n-1-i][j]=a[i][j], c[i][m-1-j]=a[i][j], d[n-1-i][m-1-j]=a[i][j];
        if(a[i][j]>a[ii][jj])ii=i,jj=j;
    }

    int lb=-1,ub=1e9;
    while(ub-lb>1)
    {
        int mid=lb+(ub-lb)/2;
        if(ok(mid))ub=mid;
        else lb=mid;
    }
    printf("%d",ub);
}

Compilation message (stderr)

joioi.c: In function 'main':
joioi.c:52:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d%d",&n,&m);
      |     ^~~~~~~~~~~~~~~~~~~
joioi.c:55:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d",a[i]+j), b[n-1-i][j]=a[i][j], c[i][m-1-j]=a[i][j], d[n-1-i][m-1-j]=a[i][j];
      |         ^~~~~~~~~~~~~~~~~~

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