oj.uz

Submission #1114033

# Submission time Handle Problem Language Result Execution time Memory
1114033 2024-11-18T06:38:24 Z Dan4Life The Kingdom of JOIOI (JOI17_joioi) C++17
60 / 100
 4000 ms 79432 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;
			}
		}
		vector<int> v,v2; v.clear();
		for(int i = 0; i < n; i++){
			v2.clear();
			for(int j = lst[i]; j <= m; j++){
				if(pref[i][j]!=j) break;
				if(!i) dp[i][j]=(j!=m);
				else{
					int pos = lower_bound(all(v),lst[i-1])-begin(v);
					if(pos!=sz(v) and v[pos]<=j) dp[i][j]=1;
				}
				if(dp[i][j]) v2.pb(j);
			}
			v.swap(v2);
		}
		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 309 ms 50512 KB Output is correct
2 Correct 313 ms 50512 KB Output is correct
3 Correct 322 ms 50512 KB Output is correct
4 Correct 165 ms 50512 KB Output is correct
5 Correct 316 ms 50580 KB Output is correct
6 Correct 191 ms 50624 KB Output is correct
7 Correct 306 ms 50512 KB Output is correct
8 Correct 298 ms 50544 KB Output is correct
9 Correct 295 ms 50512 KB Output is correct
10 Correct 272 ms 50680 KB Output is correct
11 Correct 289 ms 50512 KB Output is correct
12 Correct 276 ms 50644 KB Output is correct
13 Correct 298 ms 50512 KB Output is correct
14 Correct 300 ms 50644 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 50512 KB Output is correct
2 Correct 313 ms 50512 KB Output is correct
3 Correct 322 ms 50512 KB Output is correct
4 Correct 165 ms 50512 KB Output is correct
5 Correct 316 ms 50580 KB Output is correct
6 Correct 191 ms 50624 KB Output is correct
7 Correct 306 ms 50512 KB Output is correct
8 Correct 298 ms 50544 KB Output is correct
9 Correct 295 ms 50512 KB Output is correct
10 Correct 272 ms 50680 KB Output is correct
11 Correct 289 ms 50512 KB Output is correct
12 Correct 276 ms 50644 KB Output is correct
13 Correct 298 ms 50512 KB Output is correct
14 Correct 300 ms 50644 KB Output is correct
15 Correct 324 ms 51280 KB Output is correct
16 Correct 345 ms 53584 KB Output is correct
17 Correct 367 ms 53584 KB Output is correct
18 Correct 270 ms 53340 KB Output is correct
19 Correct 375 ms 53328 KB Output is correct
20 Correct 363 ms 51280 KB Output is correct
21 Correct 374 ms 53564 KB Output is correct
22 Correct 162 ms 53472 KB Output is correct
23 Correct 365 ms 53568 KB Output is correct
24 Correct 154 ms 51684 KB Output is correct
25 Correct 383 ms 53560 KB Output is correct
26 Correct 357 ms 53576 KB Output is correct
27 Correct 396 ms 53320 KB Output is correct
28 Correct 402 ms 53364 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 50512 KB Output is correct
2 Correct 313 ms 50512 KB Output is correct
3 Correct 322 ms 50512 KB Output is correct
4 Correct 165 ms 50512 KB Output is correct
5 Correct 316 ms 50580 KB Output is correct
6 Correct 191 ms 50624 KB Output is correct
7 Correct 306 ms 50512 KB Output is correct
8 Correct 298 ms 50544 KB Output is correct
9 Correct 295 ms 50512 KB Output is correct
10 Correct 272 ms 50680 KB Output is correct
11 Correct 289 ms 50512 KB Output is correct
12 Correct 276 ms 50644 KB Output is correct
13 Correct 298 ms 50512 KB Output is correct
14 Correct 300 ms 50644 KB Output is correct
15 Correct 324 ms 51280 KB Output is correct
16 Correct 345 ms 53584 KB Output is correct
17 Correct 367 ms 53584 KB Output is correct
18 Correct 270 ms 53340 KB Output is correct
19 Correct 375 ms 53328 KB Output is correct
20 Correct 363 ms 51280 KB Output is correct
21 Correct 374 ms 53564 KB Output is correct
22 Correct 162 ms 53472 KB Output is correct
23 Correct 365 ms 53568 KB Output is correct
24 Correct 154 ms 51684 KB Output is correct
25 Correct 383 ms 53560 KB Output is correct
26 Correct 357 ms 53576 KB Output is correct
27 Correct 396 ms 53320 KB Output is correct
28 Correct 402 ms 53364 KB Output is correct
29 Execution timed out 4046 ms 79432 KB Time limit exceeded
30 Halted 0 ms 0 KB -