Submission #516615

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
516615	2022-01-21T15:36:16 Z	Drew_	Watching (JOI13_watching)	C++17	100 / 100	123 ms	17160 KB

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.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	17064 KB	Output is correct
2	Correct	58 ms	17036 KB	Output is correct
3	Correct	56 ms	17064 KB	Output is correct
4	Correct	56 ms	16972 KB	Output is correct
5	Correct	65 ms	17068 KB	Output is correct
6	Correct	55 ms	16972 KB	Output is correct
7	Correct	57 ms	17060 KB	Output is correct
8	Correct	55 ms	17084 KB	Output is correct
9	Correct	57 ms	17072 KB	Output is correct
10	Correct	59 ms	16944 KB	Output is correct
11	Correct	58 ms	16972 KB	Output is correct
12	Correct	60 ms	17064 KB	Output is correct
13	Correct	56 ms	17092 KB	Output is correct
14	Correct	58 ms	17060 KB	Output is correct
15	Correct	59 ms	17052 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	114 ms	17100 KB	Output is correct
2	Correct	60 ms	16976 KB	Output is correct
3	Correct	99 ms	17160 KB	Output is correct
4	Correct	82 ms	17100 KB	Output is correct
5	Correct	67 ms	17100 KB	Output is correct
6	Correct	66 ms	17100 KB	Output is correct
7	Correct	79 ms	17100 KB	Output is correct
8	Correct	76 ms	17112 KB	Output is correct
9	Correct	78 ms	17100 KB	Output is correct
10	Correct	92 ms	17104 KB	Output is correct
11	Correct	72 ms	17104 KB	Output is correct
12	Correct	123 ms	17100 KB	Output is correct
13	Correct	83 ms	17096 KB	Output is correct
14	Correct	76 ms	17104 KB	Output is correct
15	Correct	71 ms	17100 KB	Output is correct