제출 #1251866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251866		selahaddin123	Watching (JOI13_watching)	C++20	100 / 100	725 ms	16168 KiB

watching

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;

bool check(const vector<int> &A,int n,int P,int Q,int w){
	int ma=min(Q,n);
	vector<vector<int>>dp(n+1,vector<int>(ma+1,INT_MAX));
	dp[0][0]=0;

	for(int i=0;i<n;++i){
		for(int q=0;q<=ma;++q){
			if(dp[i][q]==INT_MAX)continue;
			int cover_until_small=A[i]+w-1;
			int j_small=upper_bound(A.begin(),A.end(),cover_until_small)-A.begin();
			if(j_small<=n&&dp[j_small][q]>dp[i][q]+1){
				dp[j_small][q]=dp[i][q]+1;
			}

			int cover_until_big=A[i]+2*w-1;
			int j_big=upper_bound(A.begin(),A.end(),cover_until_big)-A.begin();
			if(q+1<=ma&&j_big<=n&&dp[j_big][q+1]>dp[i][q]){
				dp[j_big][q+1]=dp[i][q];
			}
		}
	}

	for(int q=0;q<=ma;++q){
		if(dp[n][q]<=P)return true;
	}
	return false;
}

int main(){
	int n,P,Q;
	cin>>n>>P>>Q;
	vector<int>A(n);
	for(int i=0;i<n;++i){
		cin>>A[i];
	}
	if(n==0){
		cout<<0<<endl;
		return 0;
	}
	sort(A.begin(),A.end());
	int low=1;
	int high=A[n-1]-A[0]+1;
	int ans=high;
	while(low<=high){
		int mid=(low+high)/2;
		if(check(A,n,P,Q,mid)){
			ans=mid;
			high=mid-1;
		}
		else{
			low=mid+1;
		}
	}
	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50