oj.uz

Submission #1114010

# Submission time Handle Problem Language Result Execution time Memory
1114010 2024-11-18T05:55:28 Z Dan4Life The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 476 ms 49856 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, a[N][N], b[N][N], c[N][N], dp[N][N], pref[N][N], lst[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;
			}
		}
		for(int i = 0; i < n; i++){
			for(int j = lst[i]; j <= m; j++){
				if(pref[i][j]!=j) break;
				if(!i) dp[i][j]=1;
				else{
					for(int k = lst[i-1]; k <= j; k++) 
						dp[i][j]|=dp[i-1][k];
				}
			}
		}
		bool ok = 0;
		for(int i = 1; i <= m; i++) ok|=dp[n-1][i];
		if(ok) return 1;
		
		memset(dp,0,sizeof(dp));
		for(int i = n-1; i >= 0; i--){
			for(int j = lst[i]; j <= m; j++){
				if(pref[i][j]!=j) break;
				if(i==n-1) dp[i][j]=1;
				else{
					for(int k = lst[i+1]; k <= j; k++) 
						dp[i][j]|=dp[i+1][k];
				}
			}
		}
		for(int i = 1; i <= m; i++) ok|=dp[0][i];
		if(ok) return 1;
	}
	return 0;
}

bool chk(int R){
	memset(b,0,sizeof(b));
	int mn = (int)1e9, mx = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			mn = min(mn, a[i][j]), mx = max(mx, a[i][j]);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			b[i][j]=(a[i][j]>mn+R?2:a[i][j]<mx-R);
	bool ok = 0;
	for(int _ : {0,1,2,3}) ok|=calc(), Rotate();
	return ok;
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> 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";
}

Compilation message

joioi.cpp: In function 'bool chk(int)':
joioi.cpp:71:10: warning: unused variable '_' [-Wunused-variable]
   71 |  for(int _ : {0,1,2,3}) ok|=calc(), Rotate();
      |          ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 49744 KB Output is correct
2 Correct 206 ms 49744 KB Output is correct
3 Correct 476 ms 48464 KB Output is correct
4 Correct 468 ms 49852 KB Output is correct
5 Correct 443 ms 49856 KB Output is correct
6 Incorrect 448 ms 48464 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 49744 KB Output is correct
2 Correct 206 ms 49744 KB Output is correct
3 Correct 476 ms 48464 KB Output is correct
4 Correct 468 ms 49852 KB Output is correct
5 Correct 443 ms 49856 KB Output is correct
6 Incorrect 448 ms 48464 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 49744 KB Output is correct
2 Correct 206 ms 49744 KB Output is correct
3 Correct 476 ms 48464 KB Output is correct
4 Correct 468 ms 49852 KB Output is correct
5 Correct 443 ms 49856 KB Output is correct
6 Incorrect 448 ms 48464 KB Output isn't correct
7 Halted 0 ms 0 KB -