oj.uz

Submission #1114042

# Submission time Handle Problem Language Result Execution time Memory
1114042 2024-11-18T06:49:24 Z Dan4Life The Kingdom of JOIOI (JOI17_joioi) C++17
60 / 100
 4000 ms 118348 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 = mx-mn;
	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 51 ms 50512 KB Output is correct
2 Correct 54 ms 50500 KB Output is correct
3 Correct 318 ms 50504 KB Output is correct
4 Correct 172 ms 50544 KB Output is correct
5 Correct 329 ms 50588 KB Output is correct
6 Correct 179 ms 50504 KB Output is correct
7 Correct 329 ms 50588 KB Output is correct
8 Correct 324 ms 50580 KB Output is correct
9 Correct 335 ms 50512 KB Output is correct
10 Correct 310 ms 50588 KB Output is correct
11 Correct 326 ms 50584 KB Output is correct
12 Correct 323 ms 50584 KB Output is correct
13 Correct 335 ms 50512 KB Output is correct
14 Correct 321 ms 50552 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 50512 KB Output is correct
2 Correct 54 ms 50500 KB Output is correct
3 Correct 318 ms 50504 KB Output is correct
4 Correct 172 ms 50544 KB Output is correct
5 Correct 329 ms 50588 KB Output is correct
6 Correct 179 ms 50504 KB Output is correct
7 Correct 329 ms 50588 KB Output is correct
8 Correct 324 ms 50580 KB Output is correct
9 Correct 335 ms 50512 KB Output is correct
10 Correct 310 ms 50588 KB Output is correct
11 Correct 326 ms 50584 KB Output is correct
12 Correct 323 ms 50584 KB Output is correct
13 Correct 335 ms 50512 KB Output is correct
14 Correct 321 ms 50552 KB Output is correct
15 Correct 58 ms 51280 KB Output is correct
16 Correct 59 ms 53320 KB Output is correct
17 Correct 256 ms 53840 KB Output is correct
18 Correct 99 ms 53492 KB Output is correct
19 Correct 243 ms 53328 KB Output is correct
20 Correct 249 ms 51280 KB Output is correct
21 Correct 357 ms 53328 KB Output is correct
22 Correct 171 ms 53588 KB Output is correct
23 Correct 380 ms 53568 KB Output is correct
24 Correct 166 ms 51280 KB Output is correct
25 Correct 387 ms 53328 KB Output is correct
26 Correct 349 ms 53328 KB Output is correct
27 Correct 353 ms 53328 KB Output is correct
28 Correct 356 ms 53448 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 50512 KB Output is correct
2 Correct 54 ms 50500 KB Output is correct
3 Correct 318 ms 50504 KB Output is correct
4 Correct 172 ms 50544 KB Output is correct
5 Correct 329 ms 50588 KB Output is correct
6 Correct 179 ms 50504 KB Output is correct
7 Correct 329 ms 50588 KB Output is correct
8 Correct 324 ms 50580 KB Output is correct
9 Correct 335 ms 50512 KB Output is correct
10 Correct 310 ms 50588 KB Output is correct
11 Correct 326 ms 50584 KB Output is correct
12 Correct 323 ms 50584 KB Output is correct
13 Correct 335 ms 50512 KB Output is correct
14 Correct 321 ms 50552 KB Output is correct
15 Correct 58 ms 51280 KB Output is correct
16 Correct 59 ms 53320 KB Output is correct
17 Correct 256 ms 53840 KB Output is correct
18 Correct 99 ms 53492 KB Output is correct
19 Correct 243 ms 53328 KB Output is correct
20 Correct 249 ms 51280 KB Output is correct
21 Correct 357 ms 53328 KB Output is correct
22 Correct 171 ms 53588 KB Output is correct
23 Correct 380 ms 53568 KB Output is correct
24 Correct 166 ms 51280 KB Output is correct
25 Correct 387 ms 53328 KB Output is correct
26 Correct 349 ms 53328 KB Output is correct
27 Correct 353 ms 53328 KB Output is correct
28 Correct 356 ms 53448 KB Output is correct
29 Correct 2028 ms 79468 KB Output is correct
30 Correct 2431 ms 90468 KB Output is correct
31 Correct 3748 ms 91156 KB Output is correct
32 Correct 1782 ms 102564 KB Output is correct
33 Correct 649 ms 99472 KB Output is correct
34 Correct 2830 ms 102672 KB Output is correct
35 Correct 2949 ms 118128 KB Output is correct
36 Correct 1501 ms 113176 KB Output is correct
37 Execution timed out 4050 ms 118348 KB Time limit exceeded
38 Halted 0 ms 0 KB -