oj.uz

답안 #568625

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568625 2022-05-25T20:14:02 Z beaconmc 구경하기 (JOI13_watching) C++14
50 / 100
 1000 ms 31700 KB 
#include <bits/stdc++.h>

typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)

using namespace std;

ll dp[2003][2003];

ll n,p,q;

vector<ll> places;


bool chk(ll a){

	FOR(i,0,2002) FOR(j,0,2002) dp[i][j] = 0;




	FOR(i,0,n+1){
		if (i>p) break;
		FOR(j,0,n+1){
			if (j>q) break;
			ll realsus = dp[i][j];
			if (realsus==n) break;

			ll sus = (upper_bound(places.begin(), places.end(), places[realsus] + a-1) - places.begin());
			ll sussy = (upper_bound(places.begin(), places.end(), places[realsus] + 2*a-1) - places.begin());




			dp[i][j+1] = max(dp[i][j+1] , sussy);
			dp[i+1][j] = max(dp[i+1][j], sus);
		}
	}



	FOR(i,0,p+1){
		FOR(j,0,q+1){
			if (dp[i][j] == n) return 1;
		}
	}



	return 0;

}

int main(){
	cin >>n>>p>>q;
	FOR(i,0,n){ 
		ll temp;
		cin >> temp;
		places.push_back(temp);
	}
	sort(places.begin(), places.end());
	p = min(p,n);
	q = min(q,n);


	ll lo = 0, hi = 10000000000;
	while (lo<hi){
		ll mid = (lo+hi)/2;
		if (chk(mid)){
			hi = mid;
		}
		else lo = mid + 1;
	}
	cout << lo;

}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 31676 KB Output is correct
2 Correct 129 ms 31672 KB Output is correct
3 Correct 130 ms 31668 KB Output is correct
4 Correct 131 ms 31676 KB Output is correct
5 Correct 131 ms 31572 KB Output is correct
6 Correct 130 ms 31680 KB Output is correct
7 Correct 128 ms 31700 KB Output is correct
8 Correct 128 ms 31668 KB Output is correct
9 Correct 129 ms 31676 KB Output is correct
10 Correct 140 ms 31680 KB Output is correct
11 Correct 131 ms 31700 KB Output is correct
12 Correct 132 ms 31688 KB Output is correct
13 Correct 125 ms 31680 KB Output is correct
14 Correct 128 ms 31676 KB Output is correct
15 Correct 127 ms 31680 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 31700 KB Output is correct
2 Correct 131 ms 31672 KB Output is correct
3 Execution timed out 1092 ms 31700 KB Time limit exceeded
4 Halted 0 ms 0 KB -