oj.uz

Submission #68523

# Submission time Handle Problem Language Result Execution time Memory
68523 2018-08-17T09:04:52 Z Windazz The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 31 ms 4536 KB 
#include <iostream>
#include <fstream>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>

#define x first
#define y second
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define bit __builtin_popcount
#define all(x) x.begin(),x.end()

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const ll INF=1e18+123;
const ld EPS=1e-9;
const int inf=1e9+123;
const int MOD=1e9+7;
const int N=2001;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};

int a[N][N],m,n;

bool ioi[N][N];

bool check(int x){
    memset(ioi,0,sizeof(ioi));
    //---1
    int mn=inf,mx=0,q=m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=q;j++){
            int curmx=max(mx,a[i][j]);
            int curmn=min(mn,a[i][j]);
            if(curmx-curmn>x){
                q=j-1;
                break;
            }
            ioi[i][j]=1;
            mx=curmx;
            mn=curmn;
        }
    }
    mn=inf,mx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!ioi[i][j]){
                mn=min(a[i][j],mn);
                mx=max(a[i][j],mx);
            }
        }
    }
    if((mx-mn)<=x){
        return 1;
    }

    //----2
    memset(ioi,0,sizeof(ioi));
    mn=inf,mx=0,q=1;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=q;j--){
            int curmx=max(mx,a[i][j]);
            int curmn=min(mn,a[i][j]);
            if(curmx-curmn>x){
                q=j+1;
                break;
            }
            ioi[i][j]=1;
            mx=curmx;
            mn=curmn;
        }
    }
    mn=inf,mx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!ioi[i][j]){
                mn=min(a[i][j],mn);
                mx=max(a[i][j],mx);
            }
        }
    }
    if((mx-mn)<=x)return 1;

    //----3
    memset(ioi,0,sizeof(ioi));
    mn=inf,mx=0,q=m;
    for(int i=n;i;i--){
        for(int j=1;j<=q;j++){
            int curmx=max(mx,a[i][j]);
            int curmn=min(mn,a[i][j]);
            if(curmx-curmn>x){
                q=j-1;
                break;
            }
            ioi[i][j]=1;
            mx=curmx;
            mn=curmn;
        }
    }
    mn=inf,mx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!ioi[i][j]){
                mn=min(a[i][j],mn);
                mx=max(a[i][j],mx);
            }
        }
    }
    if((mx-mn)<=x)return 1;

    //----4
    memset(ioi,0,sizeof(ioi));
    mn=inf,mx=0,q=1;
    for(int i=n;i;i--){
        for(int j=m;j>=q;j--){
            int curmx=max(mx,a[i][j]);
            int curmn=min(mn,a[i][j]);
            if(curmx-curmn>x){
                q=j+1;
                break;
            }
            ioi[i][j]=1;
            mx=curmx;
            mn=curmn;
        }
    }
    mn=inf,mx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!ioi[i][j]){
                mn=min(a[i][j],mn);
                mx=max(a[i][j],mx);
            }
        }
    }
    if((mx-mn)<=x)return 1;
    return 0;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    int l=0,r=1e9;
    int ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(!check(mid)){
            l=mid+1;
        }
        else{
            r=mid-1;
            ans=mid;
        }
    }
    printf("%d",ans);
    return 0;
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4220 KB Output is correct
2 Correct 13 ms 4340 KB Output is correct
3 Correct 24 ms 4520 KB Output is correct
4 Correct 25 ms 4520 KB Output is correct
5 Correct 24 ms 4520 KB Output is correct
6 Correct 23 ms 4520 KB Output is correct
7 Correct 24 ms 4520 KB Output is correct
8 Correct 28 ms 4520 KB Output is correct
9 Correct 24 ms 4520 KB Output is correct
10 Correct 28 ms 4536 KB Output is correct
11 Correct 31 ms 4536 KB Output is correct
12 Incorrect 23 ms 4536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4220 KB Output is correct
2 Correct 13 ms 4340 KB Output is correct
3 Correct 24 ms 4520 KB Output is correct
4 Correct 25 ms 4520 KB Output is correct
5 Correct 24 ms 4520 KB Output is correct
6 Correct 23 ms 4520 KB Output is correct
7 Correct 24 ms 4520 KB Output is correct
8 Correct 28 ms 4520 KB Output is correct
9 Correct 24 ms 4520 KB Output is correct
10 Correct 28 ms 4536 KB Output is correct
11 Correct 31 ms 4536 KB Output is correct
12 Incorrect 23 ms 4536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4220 KB Output is correct
2 Correct 13 ms 4340 KB Output is correct
3 Correct 24 ms 4520 KB Output is correct
4 Correct 25 ms 4520 KB Output is correct
5 Correct 24 ms 4520 KB Output is correct
6 Correct 23 ms 4520 KB Output is correct
7 Correct 24 ms 4520 KB Output is correct
8 Correct 28 ms 4520 KB Output is correct
9 Correct 24 ms 4520 KB Output is correct
10 Correct 28 ms 4536 KB Output is correct
11 Correct 31 ms 4536 KB Output is correct
12 Incorrect 23 ms 4536 KB Output isn't correct
13 Halted 0 ms 0 KB -