제출 #981246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981246		Amaarsaa	구경하기 (JOI13_watching)	C++14	50 / 100	11 ms	2652 KiB

watching

#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
ll a[2004];
ll n;
bool Can(ll x, ll s, ll small, ll large) {
	bool dp[102][102][102] = {0};
	int i, j,r;
	dp[n][small][large]= 1;
	for (i = n; i >= 1; i --) {
		for (j = 0; j <= small; j ++) {
			for ( r = 0; r <= large; r ++) {
				if ( r > 0 && dp[i][j][r]) {
					s = lower_bound(a + 1, a + n + 1, a[i] - (2 * x) + 1) - a;
					s --;
					if (s == 0) return true;
					dp[s][j][r - 1] = 1;
				}
				if ( j > 0 && dp[i][j][r]) {
					s = lower_bound(a + 1, a + n + 1, a[i] - x + 1) - a;
					s --;
					if (s == 0) return true;
					dp[s][j - 1][r] = 1;
				}
				
			}
		}
	}
	return 0;
}

int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll i, lo, hi, mid, small, large, j;
	
	cin >> n >> small >> large;
	if ( small + large >= n) {
		cout << 1 << endl;
		return 0;
	}
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	sort ( a + 1, a + n + 1);
	lo = 1;
	hi = 1e9;
	
	while ( lo < hi) {
		mid = (lo + hi)/2;
		if ( !Can(mid, n, small, large)) lo = mid + 1;
		else hi = mid;
	}
	cout << lo  << endl;
}

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

watching.cpp: In function 'int main()':
watching.cpp:38:35: warning: unused variable 'j' [-Wunused-variable]
   38 |  ll i, lo, hi, mid, small, large, j;
      |                                   ^

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