제출 #107687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107687		maruii	구경하기 (JOI13_watching)	C++14	100 / 100	143 ms	8704 KiB

watching

#include <bits/stdc++.h>
using namespace std;
int N, P, Q;
unsigned int A[2002], X[2002], Y[2002];
int dp[2001][2001];
int f(int w){
	for(int i=0; i<=N; ++i){
		X[i] = lower_bound(A+i+1, A+N+1, A[i+1]+w) - A - 1;
		Y[i] = lower_bound(A+i+1, A+N+1, A[i+1]+(w<<1)) - A - 1;
	}
	for(int i=0; i<=P; ++i){
		for(int j=0; j<=Q; ++j){
			if(i && j) dp[i][j] = max(X[dp[i-1][j]], Y[dp[i][j-1]]);
			else if(i) dp[i][j] = X[dp[i-1][j]];
			else if(j) dp[i][j] = Y[dp[i][j-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;
	Q = min(Q, N), P = min(P, N-Q);
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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