제출 #537062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537062		qwerasdfzxcl	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2947 ms	31852 KiB

joioi

    #include <bits/stdc++.h>
    using namespace std;
     
    int n, m, mn = 1e9, a[2010][2010], b[2010][2010];
     
    void rot(){
    	for(int i = 1; i <= n; i++){
    		for(int j = 1; j <= m; j++){
    			b[j][n + 1 - i] = a[i][j];
    		}
    	}
    	swap(n, m);
    	for(int i = 1; i <= n; i++){
    		for(int j = 1; j <= m; j++){
    			a[i][j] = b[i][j];
    		}
    	}
    }
     
    int can(int k){
    	for(int dum = 0; dum < 4; dum++){
    		int lst = m, omx = 0, omn = 1e9;
    		for(int i = 1; i <= n; i++){
    			for(int j = 1; j <= lst; j++){
    				if(a[i][j] > mn + k){ lst = j - 1; break; }
    			}
    			for(int j = lst + 1; j <= m; j++){
    				omx = max(omx, a[i][j]);
    				omn = min(omn, a[i][j]);
                    if(omx - omn > k) break;
    			}
                if(omx - omn > k) break;
    		}
    		if(omx - omn <= k) return 1;
    		if(dum < 3) rot();
    	}
    	return 0;
    }
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cin >> n >> m;
    	for(int i = 1; i <= n; i++){
    		for(int j = 1; j <= m; j++){
    			cin >> a[i][j];
                mn = min(mn, a[i][j]);
    		}
    	}
    	int s = 0, e = 1e9;
    	while(s <= e){
    		int mid = (s + e) / 2;
    		if(can(mid)) e = mid - 1;
    		else s = mid + 1;
    	}
    cout << s << '\n';
    }

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