Submission #31745

#	Time	Username	Problem	Language	Result	Execution time	Memory
31745		top34051	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	0 ms	80532 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
#define maxn 2005
#define inf (int)1e9
int n,m,L,R;
int p[maxn][maxn];
int mx[2][maxn][maxn], mn[2][maxn][maxn];
void prep() {
    int i,j;
    for(i=1;i<=n;i++) mx[0][i][0] = mx[1][i][m+1] = -inf;
    for(i=1;i<=n;i++) mn[0][i][0] = mn[1][i][m+1] = inf;
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) mx[0][i][j] = max(mx[0][i][j-1], p[i][j]);
    for(i=1;i<=n;i++) for(j=m;j>=1;j--) mx[1][i][j] = max(mx[1][i][j+1], p[i][j]);
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) mn[0][i][j] = min(mn[0][i][j-1], p[i][j]);
    for(i=1;i<=n;i++) for(j=m;j>=1;j--) mn[1][i][j] = min(mn[1][i][j+1], p[i][j]);
}
bool check(int val) {
    int i,j,pos,last;

    pos = m;
    for(i=1;i<=n;i++) {
        last = pos;
        pos = -1;
        for(j=0;j<=last;j++) if(mx[0][i][j]-L <= val && R-mn[1][i][j+1] <= val) pos = j;
//        printf("1) i = %d pos = %d\n",i,pos);
    }
    if(pos!=-1) return 1;

    pos = m;
    for(i=n;i>=1;i--) {
        last = pos;
        pos = -1;
        for(j=0;j<=last;j++) if(mx[0][i][j]-L <= val && R-mn[1][i][j+1] <= val) pos = j;
//        printf("2) i = %d pos = %d\n",i,pos);
    }
    if(pos!=-1) return 1;


    pos = 1;
    for(i=1;i<=n;i++) {
        last = pos;
        pos = m+2;
        for(j=m+1;j>=last;j--) if(mx[1][i][j]-L <= val && R-mn[0][i-1][j] <= val) pos = j;
//        printf("3) i = %d pos = %d\n",i,pos);
    }
    if(pos!=m+2) return 1;

    pos = 1;
    for(i=n;i>=1;i--) {
        last = pos;
        pos = m+2;
        for(j=m+1;j>=last;j--) if(mx[1][i][j]-L <= val && R-mn[0][i-1][j] <= val) pos = j;
//        printf("4) i = %d pos = %d\n",i,pos);
    }
    if(pos!=m+2) return 1;

    return 0;
}
main() {
    int i,j,l,r,mid;
    int ans;
    scanf("%d%d",&n,&m);
    L = inf; R = -inf;
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&p[i][j]), L = min(L,p[i][j]), R = max(R,p[i][j]);
    prep();
    l = 0; r = (int)1e9;
    while(l<=r) {
        mid = (l+r)/2;
//        printf("MID = %d\n",mid);
        if(check(mid)) {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
//        printf("----------------\n");
    }
    printf("%d",ans);
}

Compilation message (stderr)

joioi.cpp:59:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
joioi.cpp: In function 'int main()':
joioi.cpp:62:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
joioi.cpp:64:101: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&p[i][j]), L = min(L,p[i][j]), R = max(R,p[i][j]);
                                                                                                     ^

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