| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 306338 | syy | 구경하기 (JOI13_watching) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define sandybridge __attribute__((optimize("Ofast"), target("arch=sandybridge")))
ll n, p, q, A[2005], w, upper, lower, dp[2005][2005];
ll sandybridge f(ll index, ll bigCamsNeeded) { //Min p that can cover everything
if (index < 0) return 0;
if (dp[index][bigCamsNeeded] != -1) return dp[index][bigCamsNeeded]; //If calculated
dp[index][bigCamsNeeded] = LLONG_MAX;
if (bigCamsNeeded > 0) {
ll ind = upper_bound(A, A + n, A[index] - w - w) - A - 1; //Cannot take
dp[index][bigCamsNeeded] = f(ind, bigCamsNeeded - 1);
}
ll ind = upper_bound(A, A + n, A[index] - w) - A - 1;
dp[index][bigCamsNeeded] = min(dp[index][bigCamsNeeded], f(ind, bigCamsNeeded) + 1); // You used one more small camera so need + 1
return dp[index][bigCamsNeeded];
}
int sandybridge main() {
fastio;
cin >> n >> p >> q;
if (p + q >= n) {
cout << 1;
return 0;
}
for (ll i = 0; i < n; i++) cin >> A[i];
sort(A, A + n);
lower = 0; upper = A[n - 1] + 1;
while (upper - lower > 1) {
memset(dp, -1, sizeof dp); //Not calculated before.
w = lower + (upper - lower) / 2;
if (f(n - 1, q) <= p) upper = w;
else lower = w;
}
cout << upper;
}