oj.uz

답안 #307603

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
307603 2020-09-28T19:44:26 Z TeaTime The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 384 KB 
    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    #include <set>
    #include <map>
    #include <queue>
    #include <random>
    #include <chrono>
    #include <tuple>
    #include <random>
    #include <cmath>
     
    using namespace std;
     
    typedef unsigned long long ull;
    typedef long long ll;
    typedef long double ld;
    #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
     
    const ll SZ = 2010, INF = 1e9 * 1e9 + 10;
     
    vector<ll> vec;
     
    ll grid[SZ][SZ], pnt[SZ][SZ];
     
    ll h, w;
     
    vector<pair<ll, ll>> dir = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
     
    bool check(ll vl) {
    	for (int i = h - 1; i >= 0; i--) {
    		for (int j = 0; j < w; j++) {
    			pnt[i][j] = 0;
    		}
    	}
     
    	ll pr = 0;
    	for (int i = h - 1; i >= 0; i--) {
    		ll st = pr, lst = 0;
 
    		for (int j = pr; j < w; j++) {
    			if (i < h - 1 && abs(grid[i][j] - grid[i + 1][j]) > vl) {
    				lst = j + 1;
    			}
    			if (abs(grid[i][j] - grid[i][j - 1]) > vl) {
    				st = j;
    				break;
    			}
    		}
     
    		pr = max(lst, st);
    		for (int j = max(lst, st); j < w; j++) pnt[i][j] = 1;
    	}
     
    	for (int i = 0; i < h; i++) {
    		for (int j = 0; j < w; j++) {
    			for (auto cur : dir) {
    				if (cur.first + i >= 0 && cur.first + i < h && cur.second + j >= 0 && cur.second + j < w) {
    					ll i1 = cur.first + i, j1 = cur.second + j;
    					if (pnt[i1][j1] == pnt[i][j] && abs(grid[i][j] - grid[i1][j1]) > vl) return false;
    				}
    			}
    		}
    	}
     
    	return true;
    }
     
    int main()
    {
    	fastInp;
     
    	cin >> h >> w;
     
    	for (int i = 0; i < h; i++) {
    		for (int j = 0; j < w; j++) cin >> grid[i][j];
    	}
    	ll l = -1, r = INF;
    	while (r - l > 1) {
    		ll mid = (l + r) / 2;
    		if (mid == 10) {
    			cout << "";
    		}
    		if (check(mid)) {
    			r = mid;
    		}
    		else {
    			l = mid;
    		}
    	}
     
    	cout << r;
     
    	return 0;
    }
    /*
    4 4
    1 12 6 11
    11 10 2 14
    10 1 9 20
    4 17 19 10
     
    8 6
    23 23 10 11 16 21
    15 26 19 28 19 20
    25 26 28 16 15 11
    11 8 19 11 15 24
    14 19 15 14 24 11
    10 8 11 7 6 14
    23 5 19 23 17 17
    18 11 21 14 20 16
    */

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -