제출 #1058891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058891		vjudge1	구경하기 (JOI13_watching)	C++17	100 / 100	233 ms	14940 KiB

watching

#include <iostream>
#include <algorithm>
using namespace std;

int n, p, q, a[2005], dp[2005][2005];

int searchLowerBound(int x) {
	int l = 0, r = n - 1, m, ans = n;
	while (l <= r) {
		m = l + r >> 1;
		if (a[m] >= x) {
			r = m - 1;
			ans = m;
		}
		else l = m + 1;
	}
	return ans;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> p >> q;
	if (p + q >= n) {
		cout << 1;
		return 0;
	}
	for (int i = 0; i < n; i++) cin >> a[i];
	int l = 1, r = 1e9, w, ans = -1;
	sort(a, a + n);
	while (l <= r) {
		w = l + r >> 1;
		for (int i = 0; i <= p; i++) for (int j = 0; j <= q; j++) dp[i][j] = 0;
		for (int i = 0; i <= p; i++) for (int j = 0; j <= q; j++) {
			if (dp[i][j] == n) {
				ans = w;
				r = w - 1;
				goto end;
			}
			dp[i + 1][j] = max(dp[i + 1][j], searchLowerBound(a[dp[i][j]] + w));
			dp[i][j + 1] = max(dp[i][j + 1], searchLowerBound(a[dp[i][j]] + 2 * w));
		}
		l = w + 1;
		end:;
	}
	cout << ans;
	return 0;
}

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

watching.cpp: In function 'int searchLowerBound(int)':
watching.cpp:10:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |   m = l + r >> 1;
      |       ~~^~~
watching.cpp: In function 'int main()':
watching.cpp:32:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   w = l + r >> 1;
      |       ~~^~~

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