Submission #107681

#	Time	Username	Problem	Language	Result	Execution time	Memory
107681		maruii	Watching (JOI13_watching)	C++14	50 / 100	1061 ms	15992 KiB

watching

#include <bits/stdc++.h>
using namespace std;
int N, P, Q;
unsigned int A[2002];
int dp[2001][2001];
int f(int w){
	for(int i=0; i<=P; ++i){
		for(int j=0; j<=Q; ++j){
			if(i && j) dp[i][j] = max(lower_bound(A + dp[i-1][j] + 1, A+N+1, A[dp[i-1][j] + 1] + w), lower_bound(A + dp[i][j-1] + 1, A+N+1, A[dp[i][j-1] + 1] + (w<<1))) - A - 1;
			else if(i) dp[i][j] = lower_bound(A + dp[i-1][j] + 1, A+N+1, A[dp[i-1][j] + 1] + w) - A - 1;
			else if(j) dp[i][j] = lower_bound(A + dp[i][j-1] + 1, A+N+1, A[dp[i][j-1] + 1] + (w<<1)) - A - 1;
		}
	}
	return dp[P][Q];
}
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin>>N>>P>>Q;
	for(int i=1; i<=N; ++i) cin>>A[i];
	sort(A+1, A+N+1);
	A[N+1] = 2e9;
	P = min(P, N), Q = min(Q, N);
	int l=1, r=1e9;
	while(l<r){
		int m = l+r>>1;
		if(f(m) == N) r = m;
		else l = m+1;
	}
	cout<<l;
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l+r>>1;
           ~^~

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