Submission #1114084

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1114084	2024-11-18T07:34:24 Z	Dan4Life	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2975 ms	48340 KB

joioi

#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;
bitset<N> dp[N];
int n, m, 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 : {1,2}){
		int bst=-1,bst2,lst,sum;
		for(int i = 0; i < n; i++){
			bst2=-1; lst=0; sum = 0;
			for(int j = m-1; j>=0; j--){
				if(b[i][j]==k){ lst=j+1; break; }
			}
			for(int j = 0; j < lst; j++) 
				dp[i][j]=0, sum+=(!b[i][j] or b[i][j]==k);
			for(int j = lst; j <= m; j++){
				if(sum!=j){
					for(int k = j; k <= m; k++)dp[i][k]=0;
					break;
				}
				if(!i) dp[i][j]=(j!=m);
				else if(bst!=-1) dp[i][j]=(bst<=j);
				else dp[i][j]=0;
				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	4 ms	18768 KB	Output is correct
2	Correct	4 ms	18968 KB	Output is correct
3	Correct	13 ms	18768 KB	Output is correct
4	Correct	10 ms	18768 KB	Output is correct
5	Correct	12 ms	18980 KB	Output is correct
6	Correct	11 ms	18768 KB	Output is correct
7	Correct	11 ms	18768 KB	Output is correct
8	Correct	10 ms	18768 KB	Output is correct
9	Correct	12 ms	18912 KB	Output is correct
10	Correct	12 ms	18784 KB	Output is correct
11	Correct	12 ms	18768 KB	Output is correct
12	Correct	12 ms	18976 KB	Output is correct
13	Correct	14 ms	18768 KB	Output is correct
14	Correct	12 ms	18768 KB	Output is correct

Subtask #2
45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	18768 KB	Output is correct
2	Correct	4 ms	18968 KB	Output is correct
3	Correct	13 ms	18768 KB	Output is correct
4	Correct	10 ms	18768 KB	Output is correct
5	Correct	12 ms	18980 KB	Output is correct
6	Correct	11 ms	18768 KB	Output is correct
7	Correct	11 ms	18768 KB	Output is correct
8	Correct	10 ms	18768 KB	Output is correct
9	Correct	12 ms	18912 KB	Output is correct
10	Correct	12 ms	18784 KB	Output is correct
11	Correct	12 ms	18768 KB	Output is correct
12	Correct	12 ms	18976 KB	Output is correct
13	Correct	14 ms	18768 KB	Output is correct
14	Correct	12 ms	18768 KB	Output is correct
15	Correct	4 ms	21072 KB	Output is correct
16	Correct	8 ms	23288 KB	Output is correct
17	Correct	37 ms	21840 KB	Output is correct
18	Correct	16 ms	23120 KB	Output is correct
19	Correct	28 ms	23288 KB	Output is correct
20	Correct	29 ms	21072 KB	Output is correct
21	Correct	49 ms	23120 KB	Output is correct
22	Correct	28 ms	23120 KB	Output is correct
23	Correct	38 ms	23120 KB	Output is correct
24	Correct	21 ms	21240 KB	Output is correct
25	Correct	41 ms	21984 KB	Output is correct
26	Correct	41 ms	23120 KB	Output is correct
27	Correct	45 ms	23120 KB	Output is correct
28	Correct	50 ms	21840 KB	Output is correct

Subtask #3
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	18768 KB	Output is correct
2	Correct	4 ms	18968 KB	Output is correct
3	Correct	13 ms	18768 KB	Output is correct
4	Correct	10 ms	18768 KB	Output is correct
5	Correct	12 ms	18980 KB	Output is correct
6	Correct	11 ms	18768 KB	Output is correct
7	Correct	11 ms	18768 KB	Output is correct
8	Correct	10 ms	18768 KB	Output is correct
9	Correct	12 ms	18912 KB	Output is correct
10	Correct	12 ms	18784 KB	Output is correct
11	Correct	12 ms	18768 KB	Output is correct
12	Correct	12 ms	18976 KB	Output is correct
13	Correct	14 ms	18768 KB	Output is correct
14	Correct	12 ms	18768 KB	Output is correct
15	Correct	4 ms	21072 KB	Output is correct
16	Correct	8 ms	23288 KB	Output is correct
17	Correct	37 ms	21840 KB	Output is correct
18	Correct	16 ms	23120 KB	Output is correct
19	Correct	28 ms	23288 KB	Output is correct
20	Correct	29 ms	21072 KB	Output is correct
21	Correct	49 ms	23120 KB	Output is correct
22	Correct	28 ms	23120 KB	Output is correct
23	Correct	38 ms	23120 KB	Output is correct
24	Correct	21 ms	21240 KB	Output is correct
25	Correct	41 ms	21984 KB	Output is correct
26	Correct	41 ms	23120 KB	Output is correct
27	Correct	45 ms	23120 KB	Output is correct
28	Correct	50 ms	21840 KB	Output is correct
29	Correct	1383 ms	48200 KB	Output is correct
30	Correct	1496 ms	48336 KB	Output is correct
31	Correct	1843 ms	48336 KB	Output is correct
32	Correct	1566 ms	48096 KB	Output is correct
33	Correct	669 ms	48092 KB	Output is correct
34	Correct	1691 ms	48336 KB	Output is correct
35	Correct	2739 ms	48084 KB	Output is correct
36	Correct	1321 ms	48328 KB	Output is correct
37	Correct	2975 ms	48340 KB	Output is correct

Submission #1114084

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 40.0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
40.0 / 40.0