Submission #51464

# Submission time Handle Problem Language Result Execution time Memory
51464 2018-06-18T03:27:15 Z vovinam Watching (JOI13_watching) C++14
0 / 100
239 ms 31808 KB
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[2001], dp[2001][2001], posp[2001] , posq[2001], n , p , q;
int check(int w)
{
	memset(dp , - 1, sizeof(dp));
	for(int i = 0 ; i < n ; ++i)
	{
		posp[i] = upper_bound(a,a + n,a[i] + w - 1) - a;
		posq[i]	= upper_bound(a,a + n,a[i] +  w << 1 - 1) - a;
	}
	dp[0][0] = 0;
	for(int i = 0 ; i <= p ; ++i)
	{
		for(int j = 0 ; j <= q ; ++j)
		{
			if(dp[i][j] >= 0)
			{
				if(dp[i][j] >= n) return 1;
				dp[i + 1][j] = max(dp[i + 1][j], posp[dp[i][j]]);
				dp[i][j + 1] = max(dp[i][j + 1], posq[dp[i][j]]);
			}
		}
	}
	return 0;
}
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a

signed main(){
	cin >> n >> p >> q;
	for(int i = 0 ; i < n ; ++i)
	cin >> a[i];
	sort(a, a + n);
	int l = 1, r = 1e9, mid = (l + r) >> 1;
	while(l != r)
	{
		if(check(mid) == 1) r = mid;
		else l = mid + 1;
		mid = (l + r) >> 1;
	}
	cout << l;
}

Compilation message

watching.cpp: In function 'long long int check(long long int)':
watching.cpp:11:38: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   posq[i] = upper_bound(a,a + n,a[i] +  w << 1 - 1) - a;
                                 ~~~~~^~~~
# Verdict Execution time Memory Grader output
1 Incorrect 228 ms 31736 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 239 ms 31808 KB Output isn't correct
2 Halted 0 ms 0 KB -