Submission #397978

#	Time	Username	Problem	Language	Result	Execution time	Memory
397978		lukameladze	Watching (JOI13_watching)	C++14	100 / 100	406 ms	31856 KiB

watching

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=2005;
long long le,ri,mid,n,a[N],m,pr[N],pr1[N],dp[N][N],w,k,ans;
int check(int mid) {
	for (int i=0; i<=n; i++) {
		for (int j=0; j<=n; j++) {
			dp[i][j]=1e9;
		}
	}
	dp[0][0]=0;
	w=mid;
	for (int i=1; i<=n; i++) {
		pr[i]=pr1[i]=0;
		for (int j=i; j>=1; j--) {
			if (a[i]-a[j]>=w && !pr[i]) {
				pr[i]=j;
			//	break;
			}
			if (a[i]-a[j]>=2*w && !pr1[i]) {
				pr1[i]=j;
			//	break;
			}
		}
	//	cout<<i<<" "<<pr[i]<<" "<<pr1[i]<<endl;
	}
	for (int i=1; i<=n; i++) {
		for (int j=0; j<=min(m,(long long)i); j++) {
			if(j)
			dp[i][j]=dp[pr[i]][j-1];
			dp[i][j]=min(dp[i][j],dp[pr1[i]][j]+1);
			if (i==n && dp[n][j]<=k) return 1;
		}
	}
	//if (dp[n][m]<=k) return 1;
	return 0;
}
int main() {
	cin>>n>>m>>k;
	for (int i=1; i<=n; i++) {
		cin>>a[i];
	}
	sort(a+1, a+n+1);
	for (int i=1; i<=n; i++) {
		for (int j=i; j>=1; j--) {
			if (a[i]-a[j]>w) {
				pr[i]=j;
				break;
			}
			if (a[i]-a[j]>2*w) {
				pr1[i]=j;
				break;
			}
		}
	}
	le=1;
	ri=1e9;
	while (le<=ri) {
		mid=(le+ri)/2;
		if (check(mid)) {
			ri=mid-1;
			ans=mid;
		}
		else {
			le=mid+1;
		}
	}
	cout<<ans<<endl;
}

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