oj.uz

답안 #764686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764686 2023-06-23T21:07:05 Z NK_ 구경하기 (JOI13_watching) C++17
100 / 100
 357 ms 16116 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;

const int INF = 1e9+10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, P, Q; cin >> N >> P >> Q;
	P = min(P, N + 1), Q = min(Q, N + 1);

	V<int> A(N); for(auto& x : A) cin >> x;
	sort(begin(A), end(A));

	auto check = [&](int w) {
		V<V<int>> dp(N + 1, V<int>(P + 1, INF));
		dp[0][0] = 0;
		int RW = 0, R2W = 0;
		for(int i = 0; i < N; i++) for(int p = 0; p <= P; p++) {
			// cout << i << " <-> " << p << endl;
			if (p + 1 <= P) {
				int x = A[i] + w - 1;
				while(RW < N && A[RW] <= x) RW++;
				// cout << i << " " << RW << endl;
				dp[RW][p+1] = min(dp[RW][p+1], dp[i][p] + 1);
			}

			{
				int x = A[i] + 2 * w - 1;
				while(R2W < N && A[R2W] <= x) R2W++;
				// cout << i << " " << R2W << endl;
				dp[R2W][p] = min(dp[R2W][p], dp[i][p] + 1);
			}
			// cout << endl;
		}

		bool ans = 0;
		for(int p = 0; p <= P; p++) {
			int q = dp[N][p] - p;
			if (q <= Q) ans = 1;
		}

		return ans;
	};

	int lo = 1, hi = INF / (P + Q);
	while(lo < hi) {
		int mid = (lo + hi) / 2;

		if (check(mid)) hi = mid;
		else lo = mid + 1;
	}

	cout << lo << nl;



    return 0;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 261 ms 12244 KB Output is correct
4 Correct 357 ms 16116 KB Output is correct
5 Correct 16 ms 996 KB Output is correct
6 Correct 355 ms 16096 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 24 ms 1428 KB Output is correct
9 Correct 128 ms 6316 KB Output is correct
10 Correct 334 ms 15316 KB Output is correct
11 Correct 16 ms 1092 KB Output is correct
12 Correct 186 ms 8092 KB Output is correct
13 Correct 4 ms 496 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 6 ms 468 KB Output is correct