Submission #368019

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
368019	2021-02-19T10:19:38 Z	b23v	Watching (JOI13_watching)	C++14	100 / 100	924 ms	16256 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)
{
	memset(dp, 0x3f, sizeof dp);
	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;

			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	69 ms	16236 KB	Output is correct
2	Correct	70 ms	16108 KB	Output is correct
3	Correct	69 ms	16108 KB	Output is correct
4	Correct	68 ms	16236 KB	Output is correct
5	Correct	66 ms	16108 KB	Output is correct
6	Correct	68 ms	16108 KB	Output is correct
7	Correct	71 ms	16108 KB	Output is correct
8	Correct	66 ms	16108 KB	Output is correct
9	Correct	70 ms	16108 KB	Output is correct
10	Correct	66 ms	16108 KB	Output is correct
11	Correct	69 ms	16108 KB	Output is correct
12	Correct	71 ms	16236 KB	Output is correct
13	Correct	70 ms	16236 KB	Output is correct
14	Correct	70 ms	16108 KB	Output is correct
15	Correct	65 ms	16108 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	16236 KB	Output is correct
2	Correct	67 ms	16108 KB	Output is correct
3	Correct	706 ms	16236 KB	Output is correct
4	Correct	907 ms	16236 KB	Output is correct
5	Correct	100 ms	16108 KB	Output is correct
6	Correct	924 ms	16256 KB	Output is correct
7	Correct	77 ms	16108 KB	Output is correct
8	Correct	125 ms	16108 KB	Output is correct
9	Correct	431 ms	16108 KB	Output is correct
10	Correct	904 ms	16236 KB	Output is correct
11	Correct	119 ms	16108 KB	Output is correct
12	Correct	498 ms	16144 KB	Output is correct
13	Correct	72 ms	16108 KB	Output is correct
14	Correct	74 ms	16236 KB	Output is correct
15	Correct	74 ms	16108 KB	Output is correct