답안 #365431

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365431	2021-02-11T16:36:09 Z	farhan132	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1297 ms	102092 KB

joioi

/***Farhan132***/

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vi;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
 
#define ff first
#define ss second
#define pb push_back
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define PI 3.14159265359
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)
#define clean fflush(stdout)

const ll mod =  (ll)1e9 + 7;
const ll maxn = (ll)2e5 + 5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
//const ll INF = 1e18;
 
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};

ll a[2005][2005];
ll b[2005][2005];
ll n , m;

void rotate(){
    f1(n){
        f11(m) b[i][j] = a[i][j];
    }
    ll N = m , M = n;
    for(ll i = N; i >= 1; i--){
        for(ll j = 1; j <= M; j++) a[i][j] = b[j][N - i + 1]; 
    }
    swap(n, m);
    return;
}
ll mn = 1e12, mx = 0;
bool check(ll x){
    ll big = m;
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++){
            ll ok1 = 0, ok2 = 0;
            if(a[i][j] > x) ok1 = 1;
            if(a[i][j] < mx-x) ok2 = 1;
            if(ok1 && ok2) return 0;
            if(j > big){
                if(ok2) return 0;
            }else{
                if(ok1){
                    big = j - 1;
                } 
            }
        }
    }
    return 1;
}

void solve(){

    cin >> n >> m;
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++) cin >> a[i][j] , mn = min(mn, a[i][j]);
    }    
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++) a[i][j] -= mn , mx = max(mx, a[i][j]);
    }
    ll ans = mx;
    f1(4){
        ll lo = 0, hg = mx, res = 0;
        while(lo <= hg){
            ll mid = (lo + hg)/2;
            if(check(mid)) res = mid , hg = mid-1;
            else lo = mid+1;
        }
       ans = min(ans, res);
       rotate();
    }
    cout << ans;
    

    return;
    
}

 
int main() {
    
    
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else 
     //   freopen("cbarn2.in", "r", stdin);
     //   freopen("cbarn2.out", "w", stdout);
     ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    #endif
    //cout << fixed << setprecision(10);
   // work(maxn);
    //  mem(b,0);
    ll T;
    T=1;
    //cin >> T; 
    //scanf("%lld",&T);
   // ll CT = 0;
    //work();
    while(T--){
        //cout << "Case " << ++CT <<": " ;
        //printf("Case %lld: ",++CT);
        solve();
    }
 
    return 0;
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	2 ms	2028 KB	Output is correct
16	Correct	5 ms	2668 KB	Output is correct
17	Correct	9 ms	2924 KB	Output is correct
18	Correct	8 ms	2924 KB	Output is correct
19	Correct	10 ms	2924 KB	Output is correct
20	Correct	10 ms	2940 KB	Output is correct
21	Correct	12 ms	3052 KB	Output is correct
22	Correct	11 ms	3052 KB	Output is correct
23	Correct	16 ms	3052 KB	Output is correct
24	Correct	11 ms	2924 KB	Output is correct
25	Correct	15 ms	3052 KB	Output is correct
26	Correct	11 ms	3052 KB	Output is correct
27	Correct	11 ms	3052 KB	Output is correct
28	Correct	12 ms	3052 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	2 ms	2028 KB	Output is correct
16	Correct	5 ms	2668 KB	Output is correct
17	Correct	9 ms	2924 KB	Output is correct
18	Correct	8 ms	2924 KB	Output is correct
19	Correct	10 ms	2924 KB	Output is correct
20	Correct	10 ms	2940 KB	Output is correct
21	Correct	12 ms	3052 KB	Output is correct
22	Correct	11 ms	3052 KB	Output is correct
23	Correct	16 ms	3052 KB	Output is correct
24	Correct	11 ms	2924 KB	Output is correct
25	Correct	15 ms	3052 KB	Output is correct
26	Correct	11 ms	3052 KB	Output is correct
27	Correct	11 ms	3052 KB	Output is correct
28	Correct	12 ms	3052 KB	Output is correct
29	Correct	641 ms	85356 KB	Output is correct
30	Correct	682 ms	84716 KB	Output is correct
31	Correct	713 ms	86508 KB	Output is correct
32	Correct	614 ms	86252 KB	Output is correct
33	Correct	544 ms	82920 KB	Output is correct
34	Correct	727 ms	86388 KB	Output is correct
35	Correct	1059 ms	101960 KB	Output is correct
36	Correct	994 ms	96628 KB	Output is correct
37	Correct	1297 ms	102092 KB	Output is correct

답안 #365431

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 40.0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
40.0 / 40.0