Submission #419166

#	Time	Username	Problem	Language	Result	Execution time	Memory
419166		Runtime_error_	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	1 ms	332 KiB

joioi

#include <bits/stdc++.h>
#define ll long long
#define pi pair<ll,ll>
#define mid (l+r)/2
#define pb push
using namespace std;
const ll inf = 2e3+9,MX = 1e9+9;
ll n,m,ts,a[inf][inf],mn = MX,mx,vis[inf][inf];
pi MaxVals;
queue<ll> q;

bool check(ll k,bool is){

    q.pb(MaxVals.second);
    ts++;
    while(!q.empty()){
        ll j = q.front();
        q.pop();

        if(j<1 || j>m || vis[0][j] == ts)
            continue;
        vis[0][j] = ts;
        ll i;
        if(is){
            for(i=1;i<=n && a[i][j] >= mx-k;i++)
                vis[i][j] = ts;
            i--;
            if(i>0)
                q.pb(j-1),q.pb(j+1);
        }
        else {
            for(i=n;i>=1 && a[i][j] >= mx-k;i--)
                vis[i][j] = ts;
            i++;
            if(i<=n)
                q.pb(j-1),q.pb(j+1);
        }
    }
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=m;j++)
            if(vis[i][j] != ts && a[i][j] > mn + k)
                return 0;
    return 1;
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
                scanf("%lld",&a[i][j]);
            if(a[i][j] > mx)
                MaxVals = (pi(i,j)),mx = a[i][j];
            mn = min(mn,a[i][j]);
        }
    }

    ll l = -1, r = MX;
    while(r-l>1){
        if(check(mid,0) || check(mid,1))
            r = mid;
        else
            l = mid;
    }
    printf("%lld\n",r);
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
joioi.cpp:50:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |                 scanf("%lld",&a[i][j]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~

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