oj.uz

Submission #1012723

# Submission time Handle Problem Language Result Execution time Memory
1012723 2024-07-02T14:20:35 Z NintsiChkhaidze The Kingdom of JOIOI (JOI17_joioi) C++17
15 / 100
 27 ms 6744 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
// #define int ll
using namespace std;

const int N = 2e3 + 3;
int a[N][N],n,m,mn,mx,cnt[N];
bool vis[N][N],cur[N][N];

void clear(){
	for (int i=1;i<=n;i++)
		for(int j = 1; j <= m;j++)
			vis[i][j]=0;
}
void go(int x,int y,int d){
	if (x < 1 || y < 1 || x > n || y > m || vis[x][y]) return;
	if (a[x][y] - mn > d) return;
	vis[x][y] = 1;
	go(x+1,y,d);
	go(x-1,y,d);
	go(x,y+1,d);
	go(x,y-1,d);
}

int get(){
	int mn1=-1,mx1=-1,mn2=-1,mx2=-1;
	for (int i= 1; i <= n; i++){
		for (int j= 1;j<=m;j++){
			if(cur[i][j]){
				if (mn1 == -1) {
					mn1 = mx1 = a[i][j];
				}else{
					mn1 = min(mn1,a[i][j]);
					mx1 = max(mx1,a[i][j]);
				}
			}else{	
				if (mn2 == -1) {
					mn2 = mx2 = a[i][j];
				}else{
					mn2 = min(mn2,a[i][j]);
					mx2 = max(mx2,a[i][j]);
				}
			}
		}
	}

	return max(mx2-mn2,mx1-mn1);
}

bool go1(int d,bool dir){
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cur[i][j] = 0;

	int mnn = 2e9;
	for (int i = 1; i <= n; i++){
		mnn = min(mnn,cnt[i]);
		if (!dir){
			for (int j = m; j >= m - mnn + 1; j--){
				cur[i][j] = 1;
			}
		}else{
			for (int j = 1; j <= mnn; j++){
				cur[i][j] = 1;
			}
		}
	}
	
	return (get() <= d);
}

bool go2(int d,bool dir){
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cur[i][j] = 0;

	int mnn = 2e9;
	for (int i = n; i >= 1; i--){
		mnn = min(mnn,cnt[i]);
		if (!dir){
			for (int j = m; j >= m - mnn + 1; j--){
				cur[i][j] = 1;
			}
		}else{
			for (int j = 1; j <= mnn; j++){
				cur[i][j] = 1;
			}
		}
	}
	
	return (get() <= d);
}

signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	cin>>n>>m;

	mn = 2e9;
	int X = 0,Y=0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> a[i][j];
			if (a[i][j] < mn){
				X=i,Y=j;
				mn=a[i][j];
			}
			mx=max(mx,a[i][j]);
		}
	}

	int l = 0,r = mx - mn,ans=mx-mn;
	while (l <= r){
		clear();
		int mid=(l+r)/2;
		go(X,Y,mid);

		for (int i = 1; i <= n; i++){
			cnt[i] = m;
			for (int j = m; j >= 1; j--){
				if (!vis[i][j]){
					cnt[i] = m - j;
					break;
				}
			}
		}

		if (go1(mid,0) || go2(mid,0)){
			ans=mid;
			r=mid-1;
			continue;
		}

		for (int i = 1; i <= n; i++){
			cnt[i] = m;
			for (int j = 1; j <= m; j++){
				if (!vis[i][j]){
					cnt[i] = j - 1;
					break;
				}
			}
		}

		if (go1(mid,1) || go2(mid,1)){
			ans=mid;
			r=mid-1;
			continue;
		}

		l = mid + 1;
	}
	
	cout<<ans<<endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2512 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2512 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 7 ms 6744 KB Output is correct
17 Correct 27 ms 6116 KB Output is correct
18 Correct 15 ms 5720 KB Output is correct
19 Correct 13 ms 5436 KB Output is correct
20 Incorrect 19 ms 5600 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2512 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 7 ms 6744 KB Output is correct
17 Correct 27 ms 6116 KB Output is correct
18 Correct 15 ms 5720 KB Output is correct
19 Correct 13 ms 5436 KB Output is correct
20 Incorrect 19 ms 5600 KB Output isn't correct
21 Halted 0 ms 0 KB -