Submission #368022

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
368022	2021-02-19T10:22:17 Z	b23v	Watching (JOI13_watching)	C++14	100 / 100	956 ms	16236 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;

int dp[2005][2005];
bool check(ll w)
{
	for(int i = 0; i <= p; ++i)
	{
		dp[0][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;

			dp[i][j] = 1e5;
			if(i) dp[i][j] = dp[i - 1][j];
			dp[i][j] = min(dp[i][j], dp[i][r - 1] + 1);
			if(i) dp[i][j] = min(dp[i][j], dp[i - 1][l - 1]);
		}
	}
	return dp[p][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	4 ms	748 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	3 ms	748 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	2 ms	620 KB	Output is correct
12	Correct	2 ms	620 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	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	687 ms	12288 KB	Output is correct
4	Correct	916 ms	16108 KB	Output is correct
5	Correct	37 ms	1004 KB	Output is correct
6	Correct	956 ms	16236 KB	Output is correct
7	Correct	11 ms	620 KB	Output is correct
8	Correct	76 ms	1516 KB	Output is correct
9	Correct	399 ms	6380 KB	Output is correct
10	Correct	895 ms	15340 KB	Output is correct
11	Correct	44 ms	1004 KB	Output is correct
12	Correct	476 ms	8044 KB	Output is correct
13	Correct	5 ms	492 KB	Output is correct
14	Correct	9 ms	492 KB	Output is correct
15	Correct	6 ms	492 KB	Output is correct