oj.uz

Submission #993470

# Submission time Handle Problem Language Result Execution time Memory
993470 2024-06-05T17:51:17 Z horezushol The Kingdom of JOIOI (JOI17_joioi) C++14
60 / 100
 4000 ms 92824 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define SZ(x) ((ll)(x).size())
inline void outlast() {
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
}
const char nl = '\n';
using namespace std;
using ll = long long;
// head

const ll N = 2100;
vector<vector<ll>> a(N, vector<ll> (N, 0));
ll h, w;

vector<vector<ll>> CIRCLE(const vector<vector<ll>>& matrix) {
    vector<vector<ll>> rotated(N, vector<ll>(N));    
    for (ll i = 1; i <= h; i++) {
        for (ll j = 1; j <= w; j++) {
            rotated[j][h-i+1] = matrix[i][j];
        }
    }
    swap(h, w);
    return rotated;
}


void solve() {
	cin >> h >> w;
	for (ll i = 1; i <= h; i ++) {
		for (ll j = 1; j <= w; j ++) {
			cin >> a[i][j];
		}
	}
	ll L = 0, R = 1e9;
	while (L + 1 < R) {
		ll mid = (L + R) / 2;
		bool ok = false;
		for (ll i = 0; i < 4; i ++) {
			a = CIRCLE(a);
			ll val = LLONG_MAX, posx = 0, posy = 0;
			for (ll i = 1; i <= h; i ++) {
				for (ll j = 1; j <= w; j ++) {
					if (a[i][j] < val) {
						val = a[i][j];
						posx = i;
						posy = j;
					}
				}
			}
			vector<ll> row(N, 0);
			for (ll i = 1; i <= h; i ++) {
				for (ll j = 1; j <= w; j ++) {
					if (a[i][j] <= val + mid) {
						row[i] ++;
					} else {
						break;
					}
				}
			}
			for (ll i = 2; i <= h; i ++) {
				row[i] = min(row[i], row[i-1]);
			}
			ll mn = LLONG_MAX, mx = LLONG_MIN;
			for (ll i = 1; i <= h; i ++) {
				for (ll j = row[i]+1; j <= w; j ++) {
					mn = min(mn, a[i][j]);
					mx = max(mx, a[i][j]);
				}
			}
			if (row[posx] >= posy && (mx == LLONG_MIN || mx - mn <= mid)) {
				ok = true;
			}
		}
		if (ok) {
			R = mid;
		} else {
			L = mid;
		}
	}
	cout << R;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	// outlast();
	ll tst = 1;
	// cin >> tst;
	while (tst --) {
		solve();
		cout << nl;
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 961 ms 69792 KB Output is correct
2 Correct 933 ms 69996 KB Output is correct
3 Correct 955 ms 69796 KB Output is correct
4 Correct 1002 ms 69772 KB Output is correct
5 Correct 983 ms 69884 KB Output is correct
6 Correct 991 ms 69908 KB Output is correct
7 Correct 959 ms 69856 KB Output is correct
8 Correct 984 ms 70020 KB Output is correct
9 Correct 967 ms 69788 KB Output is correct
10 Correct 1026 ms 69796 KB Output is correct
11 Correct 989 ms 69936 KB Output is correct
12 Correct 971 ms 69784 KB Output is correct
13 Correct 998 ms 69840 KB Output is correct
14 Correct 976 ms 69740 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 961 ms 69792 KB Output is correct
2 Correct 933 ms 69996 KB Output is correct
3 Correct 955 ms 69796 KB Output is correct
4 Correct 1002 ms 69772 KB Output is correct
5 Correct 983 ms 69884 KB Output is correct
6 Correct 991 ms 69908 KB Output is correct
7 Correct 959 ms 69856 KB Output is correct
8 Correct 984 ms 70020 KB Output is correct
9 Correct 967 ms 69788 KB Output is correct
10 Correct 1026 ms 69796 KB Output is correct
11 Correct 989 ms 69936 KB Output is correct
12 Correct 971 ms 69784 KB Output is correct
13 Correct 998 ms 69840 KB Output is correct
14 Correct 976 ms 69740 KB Output is correct
15 Correct 992 ms 69812 KB Output is correct
16 Correct 1000 ms 69928 KB Output is correct
17 Correct 999 ms 70204 KB Output is correct
18 Correct 1027 ms 70056 KB Output is correct
19 Correct 1024 ms 70052 KB Output is correct
20 Correct 1091 ms 70012 KB Output is correct
21 Correct 1063 ms 70208 KB Output is correct
22 Correct 1022 ms 70148 KB Output is correct
23 Correct 1025 ms 70288 KB Output is correct
24 Correct 1014 ms 70080 KB Output is correct
25 Correct 1054 ms 70112 KB Output is correct
26 Correct 1065 ms 70152 KB Output is correct
27 Correct 1036 ms 70360 KB Output is correct
28 Correct 1037 ms 70176 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 961 ms 69792 KB Output is correct
2 Correct 933 ms 69996 KB Output is correct
3 Correct 955 ms 69796 KB Output is correct
4 Correct 1002 ms 69772 KB Output is correct
5 Correct 983 ms 69884 KB Output is correct
6 Correct 991 ms 69908 KB Output is correct
7 Correct 959 ms 69856 KB Output is correct
8 Correct 984 ms 70020 KB Output is correct
9 Correct 967 ms 69788 KB Output is correct
10 Correct 1026 ms 69796 KB Output is correct
11 Correct 989 ms 69936 KB Output is correct
12 Correct 971 ms 69784 KB Output is correct
13 Correct 998 ms 69840 KB Output is correct
14 Correct 976 ms 69740 KB Output is correct
15 Correct 992 ms 69812 KB Output is correct
16 Correct 1000 ms 69928 KB Output is correct
17 Correct 999 ms 70204 KB Output is correct
18 Correct 1027 ms 70056 KB Output is correct
19 Correct 1024 ms 70052 KB Output is correct
20 Correct 1091 ms 70012 KB Output is correct
21 Correct 1063 ms 70208 KB Output is correct
22 Correct 1022 ms 70148 KB Output is correct
23 Correct 1025 ms 70288 KB Output is correct
24 Correct 1014 ms 70080 KB Output is correct
25 Correct 1054 ms 70112 KB Output is correct
26 Correct 1065 ms 70152 KB Output is correct
27 Correct 1036 ms 70360 KB Output is correct
28 Correct 1037 ms 70176 KB Output is correct
29 Correct 3989 ms 91828 KB Output is correct
30 Correct 3805 ms 91240 KB Output is correct
31 Execution timed out 4038 ms 92824 KB Time limit exceeded
32 Halted 0 ms 0 KB -