Submission #516615

#	Time	Username	Problem	Language	Result	Execution time	Memory
516615		Drew_	Watching (JOI13_watching)	C++17	100 / 100	123 ms	17160 KiB

watching

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

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x) cerr << "[" << #x << "]: " << x << "\n";

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

constexpr ld PI = 4*atan((ld)1);
constexpr int MAX = 2069;

int n, p, q;
int ar[MAX], small[MAX], big[MAX];
int dp[MAX][MAX];

inline bool check(int w)
{
	for (int i = 1; i <= n; ++i)
	{
		small[i] = big[i] = i;
		while (small[i] < n && ar[small[i] + 1] - ar[i] + 1 <= w) small[i]++;
		while (big[i] < n && ar[big[i] + 1] - ar[i] + 1 <= 2*w) big[i]++;
	}

	memset(dp, 0, sizeof(dp));
	for (int i = 0; i <= min(n, p); ++i)
	{
		for (int j = 0; j <= min(n, q); ++j)
		{
			if (i) dp[i][j] = max(dp[i][j], small[dp[i-1][j] + 1]);
			if (j) dp[i][j] = max(dp[i][j], big[dp[i][j-1] + 1]);
			
			if (dp[i][j] == n)
				return true;
		}
	}

	return false;
}

int main()
{
	fastio;

	cin >> n >> p >> q;
	for (int i = 1; i <= n; ++i)
		cin >> ar[i];
	sort(ar+1, ar+n+1);

	int l = 1, r = 1e9;
	while (l < r)
	{
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << '\n';

	return 0;
}

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