oj.uz

Submission #1114032

# Submission time Handle Problem Language Result Execution time Memory
1114032 2024-11-18T06:36:20 Z Dan4Life The Kingdom of JOIOI (JOI17_joioi) C++17
60 / 100
 4000 ms 79412 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+1;
			}
		}
		set<int> S,S2; S.clear();
		for(int i = 0; i < n; i++){
			S2.clear();
			for(int j = lst[i]; j <= m; j++){
				if(pref[i][j]!=j) break;
				if(!i) dp[i][j]=(j!=m);
				else{
					auto itr = S.lower_bound(lst[i-1]);
					if(itr!=end(S) and *itr<=j) dp[i][j]=1;
				}
				if(dp[i][j]) S2.insert(j);
			}
			S.swap(S2);
		}
		bool ok = 0;
		for(int i = 1; i <= m; i++) ok|=dp[n-1][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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 50512 KB Output is correct
2 Correct 280 ms 50636 KB Output is correct
3 Correct 276 ms 50628 KB Output is correct
4 Correct 151 ms 50528 KB Output is correct
5 Correct 307 ms 50512 KB Output is correct
6 Correct 201 ms 50512 KB Output is correct
7 Correct 306 ms 50512 KB Output is correct
8 Correct 319 ms 50760 KB Output is correct
9 Correct 340 ms 50560 KB Output is correct
10 Correct 316 ms 50512 KB Output is correct
11 Correct 358 ms 50512 KB Output is correct
12 Correct 316 ms 50512 KB Output is correct
13 Correct 289 ms 50512 KB Output is correct
14 Correct 339 ms 50564 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 50512 KB Output is correct
2 Correct 280 ms 50636 KB Output is correct
3 Correct 276 ms 50628 KB Output is correct
4 Correct 151 ms 50528 KB Output is correct
5 Correct 307 ms 50512 KB Output is correct
6 Correct 201 ms 50512 KB Output is correct
7 Correct 306 ms 50512 KB Output is correct
8 Correct 319 ms 50760 KB Output is correct
9 Correct 340 ms 50560 KB Output is correct
10 Correct 316 ms 50512 KB Output is correct
11 Correct 358 ms 50512 KB Output is correct
12 Correct 316 ms 50512 KB Output is correct
13 Correct 289 ms 50512 KB Output is correct
14 Correct 339 ms 50564 KB Output is correct
15 Correct 314 ms 51280 KB Output is correct
16 Correct 573 ms 53624 KB Output is correct
17 Correct 539 ms 53584 KB Output is correct
18 Correct 341 ms 53576 KB Output is correct
19 Correct 427 ms 53624 KB Output is correct
20 Correct 405 ms 53624 KB Output is correct
21 Correct 393 ms 53576 KB Output is correct
22 Correct 150 ms 53576 KB Output is correct
23 Correct 344 ms 53536 KB Output is correct
24 Correct 192 ms 53608 KB Output is correct
25 Correct 391 ms 53320 KB Output is correct
26 Correct 409 ms 53320 KB Output is correct
27 Correct 452 ms 53328 KB Output is correct
28 Correct 469 ms 53544 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 50512 KB Output is correct
2 Correct 280 ms 50636 KB Output is correct
3 Correct 276 ms 50628 KB Output is correct
4 Correct 151 ms 50528 KB Output is correct
5 Correct 307 ms 50512 KB Output is correct
6 Correct 201 ms 50512 KB Output is correct
7 Correct 306 ms 50512 KB Output is correct
8 Correct 319 ms 50760 KB Output is correct
9 Correct 340 ms 50560 KB Output is correct
10 Correct 316 ms 50512 KB Output is correct
11 Correct 358 ms 50512 KB Output is correct
12 Correct 316 ms 50512 KB Output is correct
13 Correct 289 ms 50512 KB Output is correct
14 Correct 339 ms 50564 KB Output is correct
15 Correct 314 ms 51280 KB Output is correct
16 Correct 573 ms 53624 KB Output is correct
17 Correct 539 ms 53584 KB Output is correct
18 Correct 341 ms 53576 KB Output is correct
19 Correct 427 ms 53624 KB Output is correct
20 Correct 405 ms 53624 KB Output is correct
21 Correct 393 ms 53576 KB Output is correct
22 Correct 150 ms 53576 KB Output is correct
23 Correct 344 ms 53536 KB Output is correct
24 Correct 192 ms 53608 KB Output is correct
25 Correct 391 ms 53320 KB Output is correct
26 Correct 409 ms 53320 KB Output is correct
27 Correct 452 ms 53328 KB Output is correct
28 Correct 469 ms 53544 KB Output is correct
29 Execution timed out 4051 ms 79412 KB Time limit exceeded
30 Halted 0 ms 0 KB -