Submission #503399

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
503399	2022-01-07T19:49:45 Z	Abrar_Al_Samit	Watching (JOI13_watching)	C++17	100 / 100	365 ms	16212 KB

watching

#include<bits/stdc++.h>
using namespace std;
const int MX = 2001;
int n, m;
vector<int>a;
int dp[MX][MX];
int w;
int jump[MX][2];
int solve(int i, int can) {
	if(i==n) return 0;
	int &ret = dp[i][can];
	if(ret!=-1) return ret;
	ret = 1+solve(jump[i][0], can);
	if(can==0) return ret;

	ret = min(ret, solve(jump[i][1], can-1));
	return ret;
}
void PlayGround() {
	int p, q;
	cin >> n >> p >> q;
	if(p+q>=n) {
		cout << "1\n";
		return;
	}
	for(int i=0; i<n; ++i) {
		int x; cin >> x;
		a.push_back(x);
	}
	sort(a.begin(), a.end());
	int l=1, r=1e9;
	while(l<r) {
		w = (l+r)/2;
		for(int i=0; i<n; ++i) {
			jump[i][0] = lower_bound(a.begin(), a.end(), a[i]+w) - a.begin();
			jump[i][1] = lower_bound(a.begin(), a.end(), a[i]+w+w) - a.begin();
		}
		memset(dp, -1, sizeof dp);
		if(solve(0, q)<=p) {
			r = w;
		} else {
			l = w+1;
		}
	}
	cout << l << endl;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	15948 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	53 ms	15976 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	56 ms	15948 KB	Output is correct
8	Correct	53 ms	15856 KB	Output is correct
9	Correct	55 ms	15948 KB	Output is correct
10	Correct	61 ms	15972 KB	Output is correct
11	Correct	53 ms	15964 KB	Output is correct
12	Correct	53 ms	15948 KB	Output is correct
13	Correct	51 ms	15980 KB	Output is correct
14	Correct	54 ms	15964 KB	Output is correct
15	Correct	51 ms	15948 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	15948 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	55 ms	15948 KB	Output is correct
8	Correct	184 ms	16140 KB	Output is correct
9	Correct	97 ms	16036 KB	Output is correct
10	Correct	88 ms	16068 KB	Output is correct
11	Correct	365 ms	16068 KB	Output is correct
12	Correct	313 ms	16212 KB	Output is correct
13	Correct	58 ms	16020 KB	Output is correct
14	Correct	59 ms	16012 KB	Output is correct
15	Correct	57 ms	16016 KB	Output is correct