oj.uz

Submission #1114026

# Submission time Handle Problem Language Result Execution time Memory
1114026 2024-11-18T06:30:21 Z Dan4Life The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 354 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 161 ms 50512 KB Output is correct
2 Correct 173 ms 50512 KB Output is correct
3 Correct 314 ms 50624 KB Output is correct
4 Correct 152 ms 50512 KB Output is correct
5 Correct 302 ms 50512 KB Output is correct
6 Correct 202 ms 50512 KB Output is correct
7 Correct 326 ms 50624 KB Output is correct
8 Correct 317 ms 50568 KB Output is correct
9 Correct 323 ms 50624 KB Output is correct
10 Correct 323 ms 50512 KB Output is correct
11 Correct 354 ms 50512 KB Output is correct
12 Incorrect 313 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 161 ms 50512 KB Output is correct
2 Correct 173 ms 50512 KB Output is correct
3 Correct 314 ms 50624 KB Output is correct
4 Correct 152 ms 50512 KB Output is correct
5 Correct 302 ms 50512 KB Output is correct
6 Correct 202 ms 50512 KB Output is correct
7 Correct 326 ms 50624 KB Output is correct
8 Correct 317 ms 50568 KB Output is correct
9 Correct 323 ms 50624 KB Output is correct
10 Correct 323 ms 50512 KB Output is correct
11 Correct 354 ms 50512 KB Output is correct
12 Incorrect 313 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 161 ms 50512 KB Output is correct
2 Correct 173 ms 50512 KB Output is correct
3 Correct 314 ms 50624 KB Output is correct
4 Correct 152 ms 50512 KB Output is correct
5 Correct 302 ms 50512 KB Output is correct
6 Correct 202 ms 50512 KB Output is correct
7 Correct 326 ms 50624 KB Output is correct
8 Correct 317 ms 50568 KB Output is correct
9 Correct 323 ms 50624 KB Output is correct
10 Correct 323 ms 50512 KB Output is correct
11 Correct 354 ms 50512 KB Output is correct
12 Incorrect 313 ms 50512 KB Output isn't correct
13 Halted 0 ms 0 KB -