oj.uz

Submission #1114027

# Submission time Handle Problem Language Result Execution time Memory
1114027 2024-11-18T06:30:56 Z Dan4Life The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 452 ms 50624 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int N = (int)2e3+10;
int n, m, lst[N];
int dp[N][N], pref[N][N];
int a[N][N], b[N][N], c[N][N];

void Rotate(){
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			c[i][j] = b[i][j];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			b[j][i] = c[i][m-j-1];
	swap(n,m);
}

bool calc(){
	for(int k : {0,1}){
		memset(dp,0,sizeof(dp));
		memset(pref,0,sizeof(pref));
		memset(lst,0,sizeof(lst));
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				pref[i][j+1] = pref[i][j]+(!b[i][j] or b[i][j]==k);
				if(b[i][j]==k) lst[i]=j;
			}
		}
		for(int i = 0; i < n; i++){
			for(int j = lst[i]; j <= m; j++){
				if(pref[i][j]!=j) break;
				if(!i) dp[i][j]=(j!=m);
				else{
					for(int k = lst[i-1]; k <= j; k++) 
						dp[i][j]|=dp[i-1][k];
				}
			}
		}
		bool ok = 0;
		for(int i = 1; i <= m; i++) ok|=dp[n-1][i];
		if(ok) return 1;
		
		memset(dp,0,sizeof(dp));
		for(int i = n-1; i >= 0; i--){
			for(int j = lst[i]; j <= m; j++){
				if(pref[i][j]!=j) break;
				if(i==n-1) dp[i][j]=(j!=m);
				else{
					for(int k = lst[i+1]; k <= j; k++) 
						dp[i][j]|=dp[i+1][k];
				}
			}
		}
		for(int i = 1; i <= m; i++) ok|=dp[0][i];
		if(ok) return 1;
	}
	return 0;
}

int mn = (int)1e9, mx = 0;
bool chk(int R){
	memset(b,0,sizeof(b));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(a[i][j]>mn+R) b[i][j]=2;
			if(a[i][j]<mx-R){
				if(b[i][j]==2) return 0;
				b[i][j] = 1;
			}
		}
	}
	bool ok = 0;
	for(int i = 0; i < 4; i++) ok|=calc(), Rotate();
	return ok;
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> a[i][j],mn=min(mn,a[i][j]),mx=max(mx,a[i][j]);
	int l = 0, r = (int)1e9;
	while(l<r){
		int mid = (l+r)/2;
		if(chk(mid)) r=mid;
		else l=mid+1;
	}
	cout << l << "\n";
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 50608 KB Output is correct
2 Correct 201 ms 50512 KB Output is correct
3 Correct 401 ms 50624 KB Output is correct
4 Correct 197 ms 50512 KB Output is correct
5 Correct 424 ms 50512 KB Output is correct
6 Correct 254 ms 50512 KB Output is correct
7 Correct 418 ms 50380 KB Output is correct
8 Correct 452 ms 50512 KB Output is correct
9 Correct 445 ms 50512 KB Output is correct
10 Correct 427 ms 50512 KB Output is correct
11 Correct 436 ms 50512 KB Output is correct
12 Incorrect 417 ms 50512 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 50608 KB Output is correct
2 Correct 201 ms 50512 KB Output is correct
3 Correct 401 ms 50624 KB Output is correct
4 Correct 197 ms 50512 KB Output is correct
5 Correct 424 ms 50512 KB Output is correct
6 Correct 254 ms 50512 KB Output is correct
7 Correct 418 ms 50380 KB Output is correct
8 Correct 452 ms 50512 KB Output is correct
9 Correct 445 ms 50512 KB Output is correct
10 Correct 427 ms 50512 KB Output is correct
11 Correct 436 ms 50512 KB Output is correct
12 Incorrect 417 ms 50512 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 50608 KB Output is correct
2 Correct 201 ms 50512 KB Output is correct
3 Correct 401 ms 50624 KB Output is correct
4 Correct 197 ms 50512 KB Output is correct
5 Correct 424 ms 50512 KB Output is correct
6 Correct 254 ms 50512 KB Output is correct
7 Correct 418 ms 50380 KB Output is correct
8 Correct 452 ms 50512 KB Output is correct
9 Correct 445 ms 50512 KB Output is correct
10 Correct 427 ms 50512 KB Output is correct
11 Correct 436 ms 50512 KB Output is correct
12 Incorrect 417 ms 50512 KB Output isn't correct
13 Halted 0 ms 0 KB -