oj.uz

Submission #1114035

# Submission time Handle Problem Language Result Execution time Memory
1114035 2024-11-18T06:41:43 Z Dan4Life The Kingdom of JOIOI (JOI17_joioi) C++17
60 / 100
 4000 ms 102596 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;
			}
		}
		int bst=-1,bst2;
		for(int i = 0; i < n; i++){
			bst2=-1;
			for(int j = lst[i]; j <= m; j++){
				if(pref[i][j]!=j) break;
				if(!i) dp[i][j]=(j!=m);
				else if(bst!=-1) dp[i][j]=(bst<=j);
				if(dp[i][j] and bst2==-1) bst2=j;
			}
			bst=bst2;
		}
		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(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	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 280 ms 50512 KB Output is correct
2 Correct 269 ms 50512 KB Output is correct
3 Correct 267 ms 50512 KB Output is correct
4 Correct 145 ms 50684 KB Output is correct
5 Correct 294 ms 50400 KB Output is correct
6 Correct 200 ms 50512 KB Output is correct
7 Correct 315 ms 50580 KB Output is correct
8 Correct 300 ms 50512 KB Output is correct
9 Correct 297 ms 50512 KB Output is correct
10 Correct 316 ms 50580 KB Output is correct
11 Correct 287 ms 50584 KB Output is correct
12 Correct 291 ms 50512 KB Output is correct
13 Correct 306 ms 50512 KB Output is correct
14 Correct 315 ms 50588 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 50512 KB Output is correct
2 Correct 269 ms 50512 KB Output is correct
3 Correct 267 ms 50512 KB Output is correct
4 Correct 145 ms 50684 KB Output is correct
5 Correct 294 ms 50400 KB Output is correct
6 Correct 200 ms 50512 KB Output is correct
7 Correct 315 ms 50580 KB Output is correct
8 Correct 300 ms 50512 KB Output is correct
9 Correct 297 ms 50512 KB Output is correct
10 Correct 316 ms 50580 KB Output is correct
11 Correct 287 ms 50584 KB Output is correct
12 Correct 291 ms 50512 KB Output is correct
13 Correct 306 ms 50512 KB Output is correct
14 Correct 315 ms 50588 KB Output is correct
15 Correct 316 ms 51280 KB Output is correct
16 Correct 339 ms 53328 KB Output is correct
17 Correct 373 ms 53584 KB Output is correct
18 Correct 274 ms 53380 KB Output is correct
19 Correct 350 ms 54608 KB Output is correct
20 Correct 337 ms 51536 KB Output is correct
21 Correct 357 ms 53328 KB Output is correct
22 Correct 152 ms 53424 KB Output is correct
23 Correct 330 ms 53320 KB Output is correct
24 Correct 165 ms 51536 KB Output is correct
25 Correct 394 ms 53328 KB Output is correct
26 Correct 342 ms 53328 KB Output is correct
27 Correct 355 ms 53500 KB Output is correct
28 Correct 370 ms 53320 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 50512 KB Output is correct
2 Correct 269 ms 50512 KB Output is correct
3 Correct 267 ms 50512 KB Output is correct
4 Correct 145 ms 50684 KB Output is correct
5 Correct 294 ms 50400 KB Output is correct
6 Correct 200 ms 50512 KB Output is correct
7 Correct 315 ms 50580 KB Output is correct
8 Correct 300 ms 50512 KB Output is correct
9 Correct 297 ms 50512 KB Output is correct
10 Correct 316 ms 50580 KB Output is correct
11 Correct 287 ms 50584 KB Output is correct
12 Correct 291 ms 50512 KB Output is correct
13 Correct 306 ms 50512 KB Output is correct
14 Correct 315 ms 50588 KB Output is correct
15 Correct 316 ms 51280 KB Output is correct
16 Correct 339 ms 53328 KB Output is correct
17 Correct 373 ms 53584 KB Output is correct
18 Correct 274 ms 53380 KB Output is correct
19 Correct 350 ms 54608 KB Output is correct
20 Correct 337 ms 51536 KB Output is correct
21 Correct 357 ms 53328 KB Output is correct
22 Correct 152 ms 53424 KB Output is correct
23 Correct 330 ms 53320 KB Output is correct
24 Correct 165 ms 51536 KB Output is correct
25 Correct 394 ms 53328 KB Output is correct
26 Correct 342 ms 53328 KB Output is correct
27 Correct 355 ms 53500 KB Output is correct
28 Correct 370 ms 53320 KB Output is correct
29 Correct 3150 ms 79464 KB Output is correct
30 Correct 3780 ms 100988 KB Output is correct
31 Execution timed out 4053 ms 102596 KB Time limit exceeded
32 Halted 0 ms 0 KB -