oj.uz

답안 #571976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571976 2022-06-03T08:14:27 Z 1ne 구경하기 (JOI13_watching) C++14
100 / 100
 819 ms 30340 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 - 1) - arr.begin();
			long long nxt2 = lower_bound(arr.begin(),arr.end(),arr[i] + u - 1) - arr.begin();
			while((nxt==n) || (arr[nxt] - arr[i] > 2 * u - 1))--nxt;
			while((nxt2==n) || (arr[nxt2] - arr[i] > u - 1))--nxt2;
			while(nxt + 1<n && arr[nxt + 1] - arr[i] <=2 * u - 1)++nxt;
			while(nxt2 + 1<n && arr[nxt2 + 1] - arr[i] <=u - 1)++nxt2;
			for (int j = 0;j<=p;++j){
				if (dp[i][j]==LLONG_MAX)continue;
				dp[min(n,nxt + 1)][j] = min(dp[i][j] + 1,dp[min(n,nxt + 1)][j]);
				if (j + 1<=p)
					dp[min(n,nxt2 + 1)][j + 1] = min(dp[i][j],dp[min(n,nxt2 + 1)][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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 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 316 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 9 ms 596 KB Output is correct
8 Correct 59 ms 2440 KB Output is correct
9 Correct 325 ms 12336 KB Output is correct
10 Correct 819 ms 30340 KB Output is correct
11 Correct 55 ms 1908 KB Output is correct
12 Correct 459 ms 15860 KB Output is correct
13 Correct 9 ms 596 KB Output is correct
14 Correct 17 ms 756 KB Output is correct
15 Correct 17 ms 732 KB Output is correct