# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1233326 | CrabCNH | Watching (JOI13_watching) | C++20 | 1097 ms | 327680 KiB |
#include <bits/stdc++.h>
#define task "BriantheCrab"
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define szf sizeof
#define sz(s) (int)((s).size())
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}
const int maxN = 2e3 + 5;
const int inf = 1e9 + 7;
const int mod = 1e2 + 7;
// khong tu code thi khong kha len duoc dau
int n, P, Q;
int a[maxN];
bool check (int w) {
vector <vector <int>> dp (n + 2, vector <int> (P + 2, inf));
for (int i = 0; i <= P; i ++) {
dp[0][i] = 0;
}
int curP = 0, curQ = 0;
for (int i = 1; i <= n; i ++) {
while (a[i] - a[curP] + 1 > w && curP < i) {
curP ++;
}
while (a[i] - a[curQ] + 1 > w * 2 && curQ < i) {
//cout << "cc " << a[i] << ' ' << a[curQ] << '\n';
curQ ++;
//cout << a[i] - a[curQ] << ' ' << w * 2 << '\n';
}
curP -= ((a[i] - a[curP] + 1 <= w) && (curP >= 1));
curQ -= ((a[i] - a[curQ] + 1 <= 2 * w) && (curQ >= 1));
for (int j = 0; j <= P; j ++) {
// cout << "trace " << i << ' ' << curP << ' ' << curQ << '\n';
if (j >= 1) {
minimize (dp[i][j], dp[curP][j - 1]);
}
minimize (dp[i][j], dp[curQ][j] + 1);
//cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
//if (j >= 1) cout << "tr " << curP << ' ' << j - 1 << ' ' << dp[curP][j - 1] << '\n';
//cout << "tr " << curQ << ' ' << j << ' ' << dp[curQ][j] + 1 << '\n';
}
}
for (int i = 0; i <= P; i ++) {
//cout << dp[n][i] << '\n';
if (dp[n][i] <= Q) {
return true;
}
}
return false;
}
void solve () {
cin >> n >> P >> Q;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
sort (a + 1, a + n + 1);
int l = 0, r = inf, res = -1;
while (true) {
if (l > r) {
break;
}
int mid = (l + r) >> 1;
if (check (mid)) {
res = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << res;
return;
}
signed main () {
cin.tie (nullptr) -> sync_with_stdio (false);
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
int t = 1;
//cin >> t;
while (t --) {
solve ();
}
return 0;
}
// thfv
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |