oj.uz

Submission #1114073

# Submission time Handle Problem Language Result Execution time Memory
1114073 2024-11-18T07:29:40 Z Dan4Life The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 3640 ms 63820 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;
int dp[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));
		int bst=-1,bst2;
		for(int i = 0; i < n; i++){
			bst2=-1; int sum = 0, lst = 0;
			for(int j = 0; j < m; j++) if(b[i][j]==k) lst=j+1;
			for(int j = 0; j < lst; j++) sum+=(!b[i][j] or b[i][j]==k);
			for(int j = lst; j <= m; j++){
				if(sum!=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;
				sum+=(!b[i][j] or b[i][j]==k);
			}
			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 17 ms 34640 KB Output is correct
2 Correct 18 ms 34640 KB Output is correct
3 Correct 112 ms 34892 KB Output is correct
4 Correct 65 ms 34640 KB Output is correct
5 Correct 100 ms 34640 KB Output is correct
6 Correct 72 ms 34640 KB Output is correct
7 Correct 108 ms 34812 KB Output is correct
8 Correct 96 ms 34640 KB Output is correct
9 Correct 105 ms 34640 KB Output is correct
10 Correct 89 ms 34832 KB Output is correct
11 Correct 97 ms 34640 KB Output is correct
12 Correct 101 ms 34640 KB Output is correct
13 Correct 117 ms 34640 KB Output is correct
14 Correct 113 ms 34640 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34640 KB Output is correct
2 Correct 18 ms 34640 KB Output is correct
3 Correct 112 ms 34892 KB Output is correct
4 Correct 65 ms 34640 KB Output is correct
5 Correct 100 ms 34640 KB Output is correct
6 Correct 72 ms 34640 KB Output is correct
7 Correct 108 ms 34812 KB Output is correct
8 Correct 96 ms 34640 KB Output is correct
9 Correct 105 ms 34640 KB Output is correct
10 Correct 89 ms 34832 KB Output is correct
11 Correct 97 ms 34640 KB Output is correct
12 Correct 101 ms 34640 KB Output is correct
13 Correct 117 ms 34640 KB Output is correct
14 Correct 113 ms 34640 KB Output is correct
15 Correct 20 ms 35408 KB Output is correct
16 Correct 24 ms 37712 KB Output is correct
17 Correct 94 ms 37712 KB Output is correct
18 Correct 41 ms 37712 KB Output is correct
19 Correct 101 ms 37808 KB Output is correct
20 Correct 88 ms 36944 KB Output is correct
21 Correct 136 ms 37712 KB Output is correct
22 Correct 71 ms 37712 KB Output is correct
23 Correct 133 ms 37712 KB Output is correct
24 Correct 60 ms 36944 KB Output is correct
25 Correct 137 ms 37712 KB Output is correct
26 Correct 135 ms 39160 KB Output is correct
27 Correct 128 ms 38992 KB Output is correct
28 Correct 155 ms 38992 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34640 KB Output is correct
2 Correct 18 ms 34640 KB Output is correct
3 Correct 112 ms 34892 KB Output is correct
4 Correct 65 ms 34640 KB Output is correct
5 Correct 100 ms 34640 KB Output is correct
6 Correct 72 ms 34640 KB Output is correct
7 Correct 108 ms 34812 KB Output is correct
8 Correct 96 ms 34640 KB Output is correct
9 Correct 105 ms 34640 KB Output is correct
10 Correct 89 ms 34832 KB Output is correct
11 Correct 97 ms 34640 KB Output is correct
12 Correct 101 ms 34640 KB Output is correct
13 Correct 117 ms 34640 KB Output is correct
14 Correct 113 ms 34640 KB Output is correct
15 Correct 20 ms 35408 KB Output is correct
16 Correct 24 ms 37712 KB Output is correct
17 Correct 94 ms 37712 KB Output is correct
18 Correct 41 ms 37712 KB Output is correct
19 Correct 101 ms 37808 KB Output is correct
20 Correct 88 ms 36944 KB Output is correct
21 Correct 136 ms 37712 KB Output is correct
22 Correct 71 ms 37712 KB Output is correct
23 Correct 133 ms 37712 KB Output is correct
24 Correct 60 ms 36944 KB Output is correct
25 Correct 137 ms 37712 KB Output is correct
26 Correct 135 ms 39160 KB Output is correct
27 Correct 128 ms 38992 KB Output is correct
28 Correct 155 ms 38992 KB Output is correct
29 Correct 1817 ms 63700 KB Output is correct
30 Correct 1674 ms 63696 KB Output is correct
31 Correct 1926 ms 63696 KB Output is correct
32 Correct 1799 ms 63692 KB Output is correct
33 Correct 608 ms 63820 KB Output is correct
34 Correct 1930 ms 63692 KB Output is correct
35 Correct 3287 ms 63696 KB Output is correct
36 Correct 1412 ms 63692 KB Output is correct
37 Correct 3640 ms 63700 KB Output is correct