Submission #1135942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135942		gadun	Watching (JOI13_watching)	C++20	100 / 100	684 ms	16124 KiB

watching

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1e9+7;
const int INF = 1e9;
const int MAXN = 1e5+5;
const int LOG = 20;
#define ci pair<char,ll>
#define ii pair<ll,ll>
#define fi first
#define se second
#define shows(x) cerr << "[ " << x << " ]" << endl;
#define show(x) cerr << #x << " is " << x << endl;
#define f0r(n) for(int i = 1; i <= n; i++)
#define f0r2(n) for(int j = 0; j < n; j++)
//#define int long long

typedef vector<int> vi;
typedef long double ld; 

ll a[2001];
int dp[2001][2001];

int n, p, q;


bool can(ll v)
{
	memset(dp, -1, sizeof(dp));
	for(int i = 0; i <= p; i++)
	{
		for(int j = 0; j <= q; j++)
		{
			if(dp[i][j] == n-1) return true;
			dp[i+1][j]=max(dp[i+1][j], int(upper_bound(a, a+n, a[dp[i][j]+1]+v-1) - a - 1));
			dp[i][j+1] = max(dp[i][j+1], int(upper_bound(a,a+n,a[dp[i][j]+1]+2*v-1) - a - 1));
		}
	}
	return false;
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> p >> q;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	if (p + q >= n){
		cout << 1;
		return 0;
	}
	sort(a, a + n);
	ll ans = -1;
	ll lo = 1; ll hi = ll(1e9);
	ll mid;
	while(lo <= hi)
	{
		mid = (lo+hi)/2;
		if(can(mid))
		{
			hi = mid - 1;
			ans = mid;
		}
		else
		{
			lo = mid + 1;
		}
	}
	cout << ans;
}

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