oj.uz

답안 #68520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68520 2018-08-17T08:58:07 Z Windazz The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 19 ms 4616 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));
    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;
    }
    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);
            }
        }
    }
    return (mx-mn)<=x;
}

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:105: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:108: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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4216 KB Output is correct
2 Correct 12 ms 4344 KB Output is correct
3 Correct 15 ms 4424 KB Output is correct
4 Correct 18 ms 4424 KB Output is correct
5 Correct 19 ms 4612 KB Output is correct
6 Correct 17 ms 4612 KB Output is correct
7 Correct 18 ms 4612 KB Output is correct
8 Correct 15 ms 4616 KB Output is correct
9 Correct 18 ms 4616 KB Output is correct
10 Incorrect 17 ms 4616 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4216 KB Output is correct
2 Correct 12 ms 4344 KB Output is correct
3 Correct 15 ms 4424 KB Output is correct
4 Correct 18 ms 4424 KB Output is correct
5 Correct 19 ms 4612 KB Output is correct
6 Correct 17 ms 4612 KB Output is correct
7 Correct 18 ms 4612 KB Output is correct
8 Correct 15 ms 4616 KB Output is correct
9 Correct 18 ms 4616 KB Output is correct
10 Incorrect 17 ms 4616 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4216 KB Output is correct
2 Correct 12 ms 4344 KB Output is correct
3 Correct 15 ms 4424 KB Output is correct
4 Correct 18 ms 4424 KB Output is correct
5 Correct 19 ms 4612 KB Output is correct
6 Correct 17 ms 4612 KB Output is correct
7 Correct 18 ms 4612 KB Output is correct
8 Correct 15 ms 4616 KB Output is correct
9 Correct 18 ms 4616 KB Output is correct
10 Incorrect 17 ms 4616 KB Output isn't correct
11 Halted 0 ms 0 KB -