Submission #987716

#	Time	Username	Problem	Language	Result	Execution time	Memory
987716		kim	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	1 ms	348 KiB

joioi

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

int a[2005][2005];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n,m; cin>>n>>m;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>a[i][j];
    int l=0,r=1e9;
    while(l<r){
        int mid=l+r>>1;
        bool ok=1;
        int cur=m,prev=m;
        for(int i=1;ok&&i<=n;++i,prev=cur){
            for(int j=1;j<=cur;++j){
                if(i!=1&&abs(a[i-1][j]-a[i][j])>mid) cur=j-1;
                else if(j!=1&&abs(a[i][j-1]-a[i][j])>mid) cur=j-1;
            }
            for(int j=cur+1;ok&&j<=m;++j){
                if(j>prev&&abs(a[i-1][j]-a[i][j])>mid) ok=0;
                else if(j!=cur+1&&abs(a[i][j-1]-a[i][j])>mid) ok=0;
            }
        }
        if(ok){ r=mid; continue; }
        ok=1;
        cur=1,prev=1;
        for(int i=1;ok&&i<=n;++i,prev=cur){
            for(int j=m;j>=cur;--j){
                if(i!=1&&abs(a[i-1][j]-a[i][j])>mid) cur=j+1;
                else if(j!=m&&abs(a[i][j+1]-a[i][j])>mid) cur=j+1;
            }
            for(int j=cur-1;ok&&j>=1;--j){
                if(j<prev&&abs(a[i-1][j]-a[i][j])>mid) ok=0;
                else if(j!=cur-1&&abs(a[i][j+1]-a[i][j])>mid) ok=0;
            }
        }
        if(ok) r=mid;
        else l=mid+1;
    }
    cout<<l;

    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:13:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |         int mid=l+r>>1;
      |                 ~^~

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