Submission #1292190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292190		blackscreen1	Watching (JOI13_watching)	C++20	100 / 100	195 ms	31768 KiB

watching

#include <bits//stdc++.h>
using namespace std;
#define ll long long
#define st short
#define iloop(m, h) for (auto i = m; i != h; i+=(2*(m<h))-1)
#define jloop(m, h) for (auto j = m; j != h; j+=(2*(m<h))-1)
#define kloop(m, h) for (auto k = m; k != h; k+=(2*(m<h))-1)
#define getchar_unlocked _getchar_nolock
#define pll pair<ll,ll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define gll greater<ll>
#define pqll priority_queue<ll>
#define INF 1000000000000000
#define NINF -1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
//doing own problems
//problem: watching
//topic: BSTA + DP
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n, p, q;
	cin >> n >> p >> q;
	p = min(p, n);
	q = min(q, n);
	ll a[n];
	iloop(0, n) cin >> a[i];
	sort(a, a+n);
	ll dp[n][p+1], lb = 1, ub = 1000000000, mid;
	while (lb != ub) {
		mid = (lb+ub)/2;
		//cout << "mid: " << mid << "\n";
		iloop(n-1, -1) {
			ll x = lower_bound(a, a+n, a[i] + mid) - a;
			ll y = lower_bound(a, a+n, a[i] + mid*2) - a;
			if (y == n) dp[i][0] = 1;
			else dp[i][0] = dp[y][0] + 1;
			//cout << x << " " << y << ",";
			//cout << dp[i][0] << " ";
			jloop(1, p+1) {
				if (y == n) dp[i][j] = 1;
				else dp[i][j] = dp[y][j] + 1;
				if (x == n) dp[i][j] = 0;
				else dp[i][j] = min(dp[i][j], dp[x][j-1]);
				//cout << dp[i][j] << " ";
			}
			//cout << "\n";
		}
		//cout << ",\n";
		if (dp[0][p] <= q) ub = mid;
		else lb = mid + 1;
		//cout << lb << " " << ub << "e\n";
	}
	cout << lb;
}

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