Submission #1125324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125324		nuutsnoynton	Watching (JOI13_watching)	C++20	50 / 100	38 ms	1096 KiB

watching

#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 < vector < bool > > > dp(102, vector < vector < bool > > (102, vector< bool >(102, 0)));
	dp[big][small][0] = 1;
	for (i = big; i >= 0; i --) {
		for (j = small; j >= 0; j --) {
			for ( r = 0; r < n; r ++) {
				if ( dp[i][j][r] == 0) continue;
				if ( i > 0) {
					s = a[r + 1] + 2 * x ;
					s = lower_bound(a + 1, a + n + 1, s) - a - 1;
					dp[i - 1][j][s] = 1;
				}
				if ( j > 0) {
					s = a[r + 1] + x ;
					s = lower_bound(a + 1, a + n + 1, s) - a - 1;
					dp[i][j - 1][s] = 1;
				}
			}
			if ( dp[i][j][n] == 1) 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 = 1;
	hi = 1e9;
	
	while ( lo < hi) {
		mid = (lo + hi)/2;
		if ( !Can(mid)) lo = mid + 1;
		else hi = mid;
	}
	cout << lo << endl;
}

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