답안 #707952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707952	2023-03-10T15:01:30 Z	Dan4Life	구경하기 (JOI13_watching)	C++17	100 / 100	278 ms	16100 KB

watching

#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)2e3+10, LINF = (int)1e9;
int n, p, q, a[mxN], P[mxN], Q[mxN], dp[mxN][mxN];
 
bool work(int w){
	for(int i=2,j=1,k=1; i <= n; i++){
		while(a[i]-a[j]+1>w) j++;
		while(a[i]-a[k]+1>2*w) k++;
		P[i]=j-1,Q[i]=k-1;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= q; j++){
			dp[i][j] = min(LINF, dp[P[i]][j]+1);
			if(j) dp[i][j] = min(dp[i][j], dp[Q[i]][j-1]);
		}
	}
	return dp[n][q]<=p;
}
 
int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> p >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1,a+n+1);
	if(p+q>=n){cout<<1;return 0;}
	int l = 1, r = (int)1e9;
	while(l<r){
		int mid = (l+r)/2;
		if(work(mid)) r=mid;
		else l=mid+1;
	}
	cout << l;
}

Subtask #1

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	724 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct
11	Correct	1 ms	724 KB	Output is correct
12	Correct	1 ms	724 KB	Output is correct
13	Correct	1 ms	724 KB	Output is correct
14	Correct	1 ms	724 KB	Output is correct
15	Correct	1 ms	724 KB	Output is correct

Subtask #2

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	8380 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	6 ms	8404 KB	Output is correct
8	Correct	111 ms	14228 KB	Output is correct
9	Correct	22 ms	9344 KB	Output is correct
10	Correct	17 ms	9068 KB	Output is correct
11	Correct	278 ms	16084 KB	Output is correct
12	Correct	139 ms	16100 KB	Output is correct
13	Correct	7 ms	8404 KB	Output is correct
14	Correct	6 ms	8400 KB	Output is correct
15	Correct	7 ms	8404 KB	Output is correct