#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define print(x) cout << #x << " est " << x << endl;
#define x first
#define y second
#define int long long
using namespace std;
const int N = 2e3 + 5, OO = 1e14;
int nVals, nbs[2], sizes[2];
vector<int> vals;
int apres[N][2], dp[N][N];
bool possible(int w){
sizes[0] = w;
sizes[1] = 2 * w;
vector<int> pts(2, 0);
for (int i = 0; i < 2; ++i)
for (int deb = 0; deb < nVals; ++deb){
chmax(pts[i], deb);
while (pts[i] < nVals && vals[pts[i]] - vals[deb] < sizes[i])
++pts[i];
apres[deb][i] = pts[i];
}
if (false){
cout << "---" << endl;
for (int i = 0; i < nVals; ++i)
cout << apres[i][0] << " " << apres[i][1] << endl;
}
for (int i = 0; i <= nVals; ++i)
for (int j = 0; j <= nbs[0]; ++j)
dp[i][j] = OO;
dp[nVals][0] = 0;
for (int deb = nVals - 1; deb >= 0; --deb){
for (int nPris = 0; nPris <= nbs[0]; ++nPris){
if (nPris != 0) chmin(dp[deb][nPris], dp[apres[deb][0]][nPris - 1]);
chmin(dp[deb][nPris], dp[apres[deb][1]][nPris] + 1);
}
}
bool ok = false;
for (int nPris = 0; nPris <= nbs[0]; ++nPris){
ok |= (dp[0][nPris] <= nbs[1]);
if (false)
cout << nPris << ": " << dp[0][nPris] << endl;
}
return ok;
}
signed main(){
cin >> nVals >> nbs[0] >> nbs[1];
chmin(nbs[0], nVals);
vals.resize(nVals);
for (int& val : vals)
cin >> val;
sort(all(vals));
int deb = 1, fin = 1e9;
while (fin > deb){
int mid = (deb + fin)/2;
if (possible(mid))
fin = mid;
else
deb = mid + 1;
}
cout << deb << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
724 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
804 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8328 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
283 ms |
31756 KB |
Output is correct |
4 |
Correct |
362 ms |
31700 KB |
Output is correct |
5 |
Correct |
20 ms |
9556 KB |
Output is correct |
6 |
Correct |
382 ms |
31760 KB |
Output is correct |
7 |
Correct |
9 ms |
8660 KB |
Output is correct |
8 |
Correct |
27 ms |
10324 KB |
Output is correct |
9 |
Correct |
140 ms |
20180 KB |
Output is correct |
10 |
Correct |
344 ms |
31760 KB |
Output is correct |
11 |
Correct |
24 ms |
9684 KB |
Output is correct |
12 |
Correct |
191 ms |
23764 KB |
Output is correct |
13 |
Correct |
8 ms |
8532 KB |
Output is correct |
14 |
Correct |
9 ms |
8660 KB |
Output is correct |
15 |
Correct |
8 ms |
8644 KB |
Output is correct |