Submission #1125334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125334		nuutsnoynton	Synchronization (JOI13_synchronization)	C++20	0 / 100	589 ms	31876 KiB

synchronization

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
ll a[2003], big, small, n;
bool Can(ll x) {
	ll i, j, r, s;
	vector < vector < ll > > dp(2002, vector < ll > (2002, 0));
	dp[big][small] = 0;
	for (i = big; i >= 0; i --) {
		for (j = small; j >= 0; j --) {
			r = dp[i][j];
			if ( i > 0) {
				s = a[r + 1] + 2 * x ;
				s = lower_bound(a + 1, a + n + 1, s) - a - 1;
				dp[i - 1][j] = max(dp[i - 1][j], s);
			}
			if ( j > 0) {
				s = a[r + 1] + x ;
				s = lower_bound(a + 1, a + n + 1, s) - a - 1;
				dp[i][j - 1] = max ( dp[i][j - 1], s);
			}
		}
	}
	if ( dp[0][0] == n) return 1;
	return 0;
}



int main() {
	ll m, r, x, y, i, j, lo, hi, mid, ans, t;
	
	cin >> n >> small >> big;
	small = min(n, small);
	big = min(n, big);
	for (i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort ( a + 1, a + n + 1);
	lo = 0;
	hi = 1e9;
	
	while ( lo < hi) {
		mid = (lo + hi)/2;
		if ( !Can(mid)) lo = mid + 1;
		else hi = mid;
	}
	cout << lo << endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40