oj.uz

Submission #993471

# Submission time Handle Problem Language Result Execution time Memory
993471 2024-06-05T17:54:00 Z horezushol The Kingdom of JOIOI (JOI17_joioi) C++14
60 / 100
 4000 ms 104580 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));
vector<vector<ll>> rotated(N, vector<ll>(N));    
ll h, w;

vector<vector<ll>> CIRCLE(const vector<vector<ll>>& matrix) {
    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;
	vector<ll> row(N, 0);
	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;
					}
				}
			}
			for (ll i = 1; i <= h; i ++) {
				row[i] = 0;
				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 1188 ms 104388 KB Output is correct
2 Correct 1122 ms 104364 KB Output is correct
3 Correct 1207 ms 104396 KB Output is correct
4 Correct 1139 ms 104348 KB Output is correct
5 Correct 1181 ms 104472 KB Output is correct
6 Correct 1117 ms 104396 KB Output is correct
7 Correct 1142 ms 104364 KB Output is correct
8 Correct 1142 ms 104400 KB Output is correct
9 Correct 1147 ms 104336 KB Output is correct
10 Correct 1190 ms 104564 KB Output is correct
11 Correct 1161 ms 104440 KB Output is correct
12 Correct 1144 ms 104392 KB Output is correct
13 Correct 1139 ms 104388 KB Output is correct
14 Correct 1142 ms 104372 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1188 ms 104388 KB Output is correct
2 Correct 1122 ms 104364 KB Output is correct
3 Correct 1207 ms 104396 KB Output is correct
4 Correct 1139 ms 104348 KB Output is correct
5 Correct 1181 ms 104472 KB Output is correct
6 Correct 1117 ms 104396 KB Output is correct
7 Correct 1142 ms 104364 KB Output is correct
8 Correct 1142 ms 104400 KB Output is correct
9 Correct 1147 ms 104336 KB Output is correct
10 Correct 1190 ms 104564 KB Output is correct
11 Correct 1161 ms 104440 KB Output is correct
12 Correct 1144 ms 104392 KB Output is correct
13 Correct 1139 ms 104388 KB Output is correct
14 Correct 1142 ms 104372 KB Output is correct
15 Correct 1168 ms 104384 KB Output is correct
16 Correct 1169 ms 104392 KB Output is correct
17 Correct 1196 ms 104328 KB Output is correct
18 Correct 1171 ms 104580 KB Output is correct
19 Correct 1179 ms 104556 KB Output is correct
20 Correct 1224 ms 104332 KB Output is correct
21 Correct 1177 ms 104432 KB Output is correct
22 Correct 1189 ms 104384 KB Output is correct
23 Correct 1187 ms 104384 KB Output is correct
24 Correct 1188 ms 104364 KB Output is correct
25 Correct 1155 ms 104324 KB Output is correct
26 Correct 1163 ms 104560 KB Output is correct
27 Correct 1167 ms 104332 KB Output is correct
28 Correct 1181 ms 104428 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1188 ms 104388 KB Output is correct
2 Correct 1122 ms 104364 KB Output is correct
3 Correct 1207 ms 104396 KB Output is correct
4 Correct 1139 ms 104348 KB Output is correct
5 Correct 1181 ms 104472 KB Output is correct
6 Correct 1117 ms 104396 KB Output is correct
7 Correct 1142 ms 104364 KB Output is correct
8 Correct 1142 ms 104400 KB Output is correct
9 Correct 1147 ms 104336 KB Output is correct
10 Correct 1190 ms 104564 KB Output is correct
11 Correct 1161 ms 104440 KB Output is correct
12 Correct 1144 ms 104392 KB Output is correct
13 Correct 1139 ms 104388 KB Output is correct
14 Correct 1142 ms 104372 KB Output is correct
15 Correct 1168 ms 104384 KB Output is correct
16 Correct 1169 ms 104392 KB Output is correct
17 Correct 1196 ms 104328 KB Output is correct
18 Correct 1171 ms 104580 KB Output is correct
19 Correct 1179 ms 104556 KB Output is correct
20 Correct 1224 ms 104332 KB Output is correct
21 Correct 1177 ms 104432 KB Output is correct
22 Correct 1189 ms 104384 KB Output is correct
23 Correct 1187 ms 104384 KB Output is correct
24 Correct 1188 ms 104364 KB Output is correct
25 Correct 1155 ms 104324 KB Output is correct
26 Correct 1163 ms 104560 KB Output is correct
27 Correct 1167 ms 104332 KB Output is correct
28 Correct 1181 ms 104428 KB Output is correct
29 Execution timed out 4041 ms 104256 KB Time limit exceeded
30 Halted 0 ms 0 KB -