oj.uz

Submission #1003761

# Submission time Handle Problem Language Result Execution time Memory
1003761 2024-06-20T16:53:01 Z vako_p The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 0 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
 
const int mxN = 2e3 + 5;
ll n,m,a[mxN][mxN],p[mxN][mxN],b[mxN][mxN],x,y;
bool vis[mxN][mxN];
 
bool turn(ll mid){
	for(int j = 1; j <= m; j++){
		for(int i = n; i > 0; i--){
			b[j][n - i + 1] = a[i][j]; 
		}
	}
	swap(x, y);
	y = n - y + 1;
	swap(m, n);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			a[i][j] = b[i][j];
			p[i][j] = max(p[i - 1][j], p[i][j - 1]);
			p[i][j] = max(p[i][j], a[i][j]);
			vis[i][j] = false;
		}
	}
	if(p[x][y] - a[x][y] > mid) return false;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(p[i][j] - a[x][y] > mid) break;
			vis[i][j] = true;
		}
	} 
	ll mx = 0, mn = 1e17;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(vis[i][j]) continue;
			mn = min(mn, a[i][j]);
			mx = max(mx, a[i][j]);
		}
	}
	return (mx - mn <= mid);
}
 
bool ok(ll mid){
	return (turn(mid) or turn(mid) or turn(mid) or turn(mid));
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	ll mn = 1e17;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			if(mn > a[i][j]){
				x = i;
				y = j;
				mn = a[i][j];
			}
		}
	}
	ll l = 0, r = 1e9;
	while(r > l + 1){
		ll mid = l + (r - l) / 2;
		if(ok(mid)) r = mid;
		else l = mid;
	}
	cout << r;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Incorrect 0 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Incorrect 0 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Incorrect 0 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -