Submission #368016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
368016	2021-02-19T10:13:37 Z	b23v	Watching (JOI13_watching)	C++17	100 / 100	893 ms	576 KB

watching

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <climits>
#include <cstring>
#include <deque>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using ii = pair<int,int>;
using vii = vector<pair<int,int>>;
using vb = vector<bool>;
template<typename T>
using Graph = vector<vector<T>>;

int n, p, q;
vector<ll> A;

bool check(ll w)
{
	vi dp(n + 1, 1e5), dp1(n + 1, 1e5);
	for(int i = 0; i <= p; ++i)
	{
		dp1[0] = 0;
		int l = 1, r = 1;
		for(int j = 1; j <= n; ++j)
		{
			while(l <= n && A[l] < A[j] - w + 1) ++l;
			while(r <= n && A[r] < A[j] - 2 * w + 1) ++r;

			dp1[j] = min(dp1[j], dp1[r - 1] + 1);
			dp1[j] = min(dp1[j], dp[l - 1]);
		}
		dp = dp1;
	}
	return dp[n] <= q;
}

void solve()
{
	cin >> n >> p >> q;
	p = min(n, p);
	A.assign(n + 1, 0);
	
	for(int i = 1; i <= n; ++i) cin >> A[i];
	sort(A.begin(), A.end());

	ll ans = -1;
	ll L = 1, R = ll(1e9);
	while(L <= R)
	{
		ll mid = L + (R - L) / 2;
		if(check(mid))
		{
			ans = mid;
			R = mid - 1;
		} else
		{
			L = mid + 1;
		}
	}
	cout << ans << '\n';
}

int main ()
{
#ifdef LOCAL
   freopen("input.txt", "rt", stdin);
   freopen("output.txt", "wt", stdout);
#endif

   	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tc = 1; 
//	cin >> tc;
	while(tc--) solve();
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	2 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	3 ms	364 KB	Output is correct
12	Correct	2 ms	492 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	731 ms	420 KB	Output is correct
4	Correct	879 ms	448 KB	Output is correct
5	Correct	36 ms	396 KB	Output is correct
6	Correct	893 ms	448 KB	Output is correct
7	Correct	8 ms	364 KB	Output is correct
8	Correct	66 ms	364 KB	Output is correct
9	Correct	407 ms	448 KB	Output is correct
10	Correct	860 ms	492 KB	Output is correct
11	Correct	43 ms	576 KB	Output is correct
12	Correct	455 ms	492 KB	Output is correct
13	Correct	5 ms	364 KB	Output is correct
14	Correct	6 ms	364 KB	Output is correct
15	Correct	6 ms	364 KB	Output is correct