답안 #503397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
503397	2022-01-07T19:47:36 Z	Abrar_Al_Samit	구경하기 (JOI13_watching)	C++17	50 / 100	1000 ms	16108 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 solve(int i, int can) {
	if(i==n) return 0;
	int &ret = dp[i][can];
	if(ret!=-1) return ret;
	int j = lower_bound(a.begin(), a.end(), a[i]+w) - a.begin();
	ret = 1+solve(j, can);
	if(can==0) return ret;

	j = lower_bound(a.begin(), a.end(), a[i]+2*w) - a.begin();
	ret = min(ret, solve(j, 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;
		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

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	15956 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	50 ms	15964 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	50 ms	15884 KB	Output is correct
8	Correct	51 ms	15964 KB	Output is correct
9	Correct	50 ms	15964 KB	Output is correct
10	Correct	55 ms	15968 KB	Output is correct
11	Correct	50 ms	15960 KB	Output is correct
12	Correct	53 ms	15960 KB	Output is correct
13	Correct	50 ms	15948 KB	Output is correct
14	Correct	53 ms	15968 KB	Output is correct
15	Correct	53 ms	15968 KB	Output is correct

Subtask #2

0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	51 ms	15960 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	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	15980 KB	Output is correct
8	Correct	679 ms	16064 KB	Output is correct
9	Correct	185 ms	16064 KB	Output is correct
10	Correct	186 ms	16108 KB	Output is correct
11	Execution timed out	1095 ms	16092 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-