oj.uz

답안 #571978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571978 2022-06-03T08:15:34 Z 1ne 구경하기 (JOI13_watching) C++14
100 / 100
 686 ms 30380 KB 
#include<bits/stdc++.h>
using namespace std;
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n,p,q;cin>>n>>p>>q;
	vector<long long>arr(n);
	for (long long i = 0;i<n;++i)cin>>arr[i];
	sort(arr.begin(),arr.end());
	long long left = 1,right = 1e10;
	if (p + q >=n){
		cout<<1<<'\n';
		return 0;
	}
	long long ans = right;
	function<bool(long long)>check = [&](long long u){
		vector<vector<pair<int,int>>>adj(n);
		p = min(p,n);
		vector<vector<long long>>dp(n + 1,vector<long long>(p + 1,LLONG_MAX));
		dp[0][0] = 0;
		for (int i = 0;i<n;++i){
			long long nxt = lower_bound(arr.begin(),arr.end(),arr[i] + 2 * u) - arr.begin();
			long long nxt2 = lower_bound(arr.begin(),arr.end(),arr[i] + u) - arr.begin();
			for (int j = 0;j<=p;++j){
				if (dp[i][j]==LLONG_MAX)continue;
				dp[nxt][j] = min(dp[i][j] + 1,dp[nxt][j]);
				if (j + 1<=p)
					dp[nxt2][j + 1] = min(dp[i][j],dp[nxt2][j + 1]);
			}
		}
		for (int i = 0;i<=p;++i){
			if (dp[n][i]<=q)return true;
		}
		return false;
	};
	while(left<=right){
		long long mid = (left + right)>>1;
		if (check(mid)){
			right = mid - 1;
			ans = mid;
		}
		else{
			left = mid + 1;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 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 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 0 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 8 ms 596 KB Output is correct
8 Correct 51 ms 2436 KB Output is correct
9 Correct 265 ms 12408 KB Output is correct
10 Correct 686 ms 30380 KB Output is correct
11 Correct 40 ms 1932 KB Output is correct
12 Correct 389 ms 15860 KB Output is correct
13 Correct 8 ms 596 KB Output is correct
14 Correct 11 ms 740 KB Output is correct
15 Correct 10 ms 708 KB Output is correct