Submission #211211

#	Time	Username	Problem	Language	Result	Execution time	Memory
211211		GioChkhaidze	Watching (JOI13_watching)	C++14	100 / 100	286 ms	16120 KiB

watching

#include <bits/stdc++.h>
using namespace std;
const int N=2003;
int n,P,Q,a[N];
int dp[N][N];

bool check(int w) {
	for (int i=0; i<=n; i++)
		for (int j=0; j<=Q; j++)	
			dp[i][j]=1e9;
	
	dp[0][0]=0;
	for (int i=1; i<=n; i++) {
		int indp=1,indq=1;
		for (int j=i; j>=1; j--) {
			if (a[i]-a[j]+1<=2*w) indq=j;
			if (a[i]-a[j]+1<=w) indp=j;
		}	
		for (int j=0; j<=Q; j++) 
			if (j)
					dp[i][j]=min(dp[indp-1][j]+1,dp[indq-1][j-1]);
				else 
					dp[i][j]=dp[indp-1][j]+1;
	}
	
	int res=1e9;
	for (int i=0; i<=Q; i++) 
		if (dp[n][i]!=-1) res=min(res,dp[n][i]);
	return (res<=P);
}

main () {
	cin>>n>>P>>Q;
	
	Q=min(n,Q);

	for (int i=1; i<=n; i++) 
		cin>>a[i];
		
	sort(a+1,a+n+1);

	int l=1,r=1e9,mid,ans=-1;
	while (l<=r) {
		mid=(l+r)/2;
		if (check(mid)) 
				r=mid-1,ans=mid;
			else 
				l=mid+1;
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

watching.cpp:32:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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