oj.uz

Submission #1114048

# Submission time Handle Problem Language Result Execution time Memory
1114048 2024-11-18T07:07:51 Z Dan4Life The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 20 ms 20984 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+2;
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}){
		for(int i = 0; i < n; i++) dp[i].reset();
		int bst=-1,bst2,lst;
		for(int i = 0; i < n; i++){
			bst2=-1; lst=0; int sum = 0;
			for(int j = m-1; j>=0; j--){
				if(b[i][j]==k){ lst=j+1; break; }
			}
			for(int j = 0; j <= m; j++){
				if(sum==j){
					if(!i) dp[i][j]=(j>=lst and j!=m);
					else if(bst!=-1) dp[i][j]=(j>=lst and bst<=j);
					if(dp[i][j] and bst2==-1) bst2=j; 
				}
				else dp[i][j]=0;
				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 and !ok; 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+1;
	while(l<r){
		int mid = (l+r)/2;
		if(chk(mid)) r=mid;
		else l=mid+1;
	}
	cout << l << "\n";
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20816 KB Output is correct
2 Correct 6 ms 20816 KB Output is correct
3 Correct 20 ms 20816 KB Output is correct
4 Correct 15 ms 20984 KB Output is correct
5 Correct 14 ms 20816 KB Output is correct
6 Incorrect 15 ms 20828 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20816 KB Output is correct
2 Correct 6 ms 20816 KB Output is correct
3 Correct 20 ms 20816 KB Output is correct
4 Correct 15 ms 20984 KB Output is correct
5 Correct 14 ms 20816 KB Output is correct
6 Incorrect 15 ms 20828 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20816 KB Output is correct
2 Correct 6 ms 20816 KB Output is correct
3 Correct 20 ms 20816 KB Output is correct
4 Correct 15 ms 20984 KB Output is correct
5 Correct 14 ms 20816 KB Output is correct
6 Incorrect 15 ms 20828 KB Output isn't correct
7 Halted 0 ms 0 KB -