oj.uz

답안 #571969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571969 2022-06-03T08:12:14 Z 1ne 구경하기 (JOI13_watching) C++14
0 / 100
 686 ms 31932 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 = 0,right = 1e10;
	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,INT_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]==INT_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]);
			}
		}
		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
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 468 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 557 ms 24032 KB Output is correct
4 Correct 680 ms 31908 KB Output is correct
5 Correct 36 ms 1676 KB Output is correct
6 Correct 686 ms 31932 KB Output is correct
7 Incorrect 7 ms 724 KB Output isn't correct
8 Halted 0 ms 0 KB -