oj.uz

Submission #211211

# Submission time Handle Problem Language Result Execution time Memory
211211 2020-03-19T12:33:30 Z GioChkhaidze Watching (JOI13_watching) C++14
100 / 100
 286 ms 16120 KB 
#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

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

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 6 ms 768 KB Output is correct
7 Correct 6 ms 768 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 5 ms 768 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 8320 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 245 ms 16000 KB Output is correct
4 Correct 91 ms 8960 KB Output is correct
5 Correct 282 ms 16120 KB Output is correct
6 Correct 286 ms 16000 KB Output is correct
7 Correct 84 ms 8448 KB Output is correct
8 Correct 171 ms 14312 KB Output is correct
9 Correct 99 ms 9344 KB Output is correct
10 Correct 98 ms 9088 KB Output is correct
11 Correct 273 ms 16120 KB Output is correct
12 Correct 194 ms 16000 KB Output is correct
13 Correct 85 ms 8564 KB Output is correct
14 Correct 83 ms 8448 KB Output is correct
15 Correct 83 ms 8448 KB Output is correct