Submission #1251813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251813		XXBabaProBerkay	Watching (JOI13_watching)	C++20	50 / 100	397 ms	4464 KiB

watching

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

#define F first
#define S second
#define MP make_pair
#define PB push_back

using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using pll = pair<ll, ll>;

template<typename T>
using vec = vector<T>;

template<typename T, int N>
using arr = array<T, N>;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

const int INF = 1e9 + 7;

int dp[101][101][101];

int main()
{
	cin.tie(0) -> sync_with_stdio(0);

	int N, P, Q;
	cin >> N >> P >> Q;
	vec<int> A(N + 1);
	for (int i = 1; i <= N; i++)
		cin >> A[i];

	sort(A.begin() + 1, A.end());

	auto f = [&](int w)
	{
		memset(dp, 0, sizeof dp);
		for (int i = 1; i <= N; i++)
			for (int j = 0; j <= min(P, N); j++)
				for (int k = 0; k <= min(Q, N); k++)
				{
					int x = upper_bound(A.begin() + 1, A.end(), A[i] - w) - A.begin();
					int y = upper_bound(A.begin() + 1, A.end(), A[i] - 2 * w) - A.begin();
					x--; y--;
					dp[i][j][k] = INF;
					if (j) dp[i][j][k] = min(dp[i][j][k], dp[x][j - 1][k]);
					if (k) dp[i][j][k] = min(dp[i][j][k], dp[y][j][k - 1]);
				}

		return (dp[N][min(P, N)][min(Q, N)] != INF);
	};

	int l = 1, r = 1e9;
	while (l <= r)
	{
		int m = (l + r) / 2;

		if (f(m)) r = m - 1;
		else l = m + 1;
	}

	cout << l << '\n';
}

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