Submission #384200

#	Time	Username	Problem	Language	Result	Execution time	Memory
384200		aryan12	구경하기 (JOI13_watching)	C++17	100 / 100	249 ms	32492 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2010;
int a[N + 20];
int dp[N + 20][N + 20];
int n;

bool Cost(int w, int p, int q) {
	int forP[n + 1], forQ[n + 1];
	for(int i = 0; i <= n; i++) {
		forP[i] = 0;
		forQ[i] = 0;
	}
	int prev = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = prev; j <= n; j++) {
			if(a[j] - a[i] >= w) {
				prev = j;
				break;
			}
			else if(j == n) {
				prev = n + 1;
			}
		}
		forP[i] = prev - 1;
	}
	prev = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = prev; j <= n; j++) {
			if(a[j] - a[i] >= 2 * w) {
				prev = j;
				break;
			}
			else if(j == n) {
				prev = n + 1;
			}
		}
		forQ[i] = prev - 1;
	}
	/*cout << "forP array\n";
	for(int i = 1; i <= n; i++) {
		cout << forP[i] << " ";
	}
	cout << "\n";
	cout << "forQ array\n";
	for(int i = 1; i <= n; i++) {
		cout << forQ[i] << " ";
	}
	cout << "\n";*/
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			dp[i][j] = 0;
		}
	}
	for(int i = 1; i <= p; i++) {
		dp[i][0] = (dp[i - 1][0] == n) ? dp[i - 1][0] : forP[dp[i - 1][0] + 1];
	}
	for(int j = 1; j <= q; j++) {
		dp[0][j] = (dp[0][j - 1] == n) ? dp[0][j - 1] : forQ[dp[0][j - 1] + 1];
	}
	for(int i = 1; i <= p; i++) {
		for(int j = 1; j <= q; j++) {
			if(dp[i - 1][j] == n || dp[i][j - 1] == n) {
				dp[i][j] = n;
				continue;
			}
			dp[i][j] = max((forP[dp[i - 1][j] + 1]), (forQ[dp[i][j - 1] + 1]));
		}
	}
	if(dp[p][q] == n)
		return true;
	return false;
}

void Solve() {
	int p, q;
	cin >> n >> p >> q;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	if(p + q >= n) {
		cout << "1\n";
		return;
	}
	int left = 1, right = 1e9;
	int mid, ans = 1e9 + 1;
	while(left <= right) {
		//cout << "left = " << left << ", right = " << right << "\n";
		mid = (left + right) / 2;
		//cout << "mid = " << mid << "\n";
		if(Cost(mid, p, q)) {
			//cout << "mid is coming true\n";
			right = mid - 1;
			ans = mid;
		}
		else {
			//cout << "mid is coming false\n";
			left = mid + 1;
		}
	}
	cout << ans << "\n";
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Solve();
	return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50