QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353180 | #958. Lockout vs tourist | HKOI0# | TL | 1807ms | 20412kb | C++20 | 1.5kb | 2024-03-13 22:34:54 | 2024-03-13 22:34:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef long double LD;
LD dp[1 << 22];
int a[22];
void solve() {
int n; cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int msk = 1; msk < (1 << n); msk++) {
vector<pair<LD, LD>> win;
for (int j = 0; j < n; j++) {
if (msk & (1 << j)) {
win.push_back({dp[msk ^ (1 << j)], a[j]});
}
}
sort(win.begin(), win.end(), [](auto a, auto b){
return a.first > b.first;
});
LD lo = 0, hi = 1e9;
while (hi - lo > 1e-12) {
LD R = 1;
LD mid = (lo + hi) / 2;
for (int j = 0; j < win.size(); j++) {
if (win[j].first >= win[j].second - 1e-12) continue;
if (win[j].second > mid) {
R -= (win[j].second - mid) / (win[j].second - win[j].first);
}
}
if (R >= 0) {
hi = mid;
} else {
lo = mid;
}
}
LD cur_ans = lo;
for (int j = 0; j < win.size(); j++) {
dp[msk] = max(dp[msk], win[j].first);
}
dp[msk] = cur_ans;
}
cout << fixed << setprecision(10);
cout << dp[(1 << n) - 1] << endl;
}
signed main() {
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3952kb
input:
2 6 7
output:
3.2307692308
result:
ok found '3.2307692', expected '3.2307692', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
3 1 1 1
output:
0.8333333333
result:
ok found '0.8333333', expected '0.8333333', error '0.0000000'
Test #3:
score: 0
Accepted
time: 3ms
memory: 3844kb
input:
11 1 2 3 4 5 6 7 8 9 10 11
output:
9.4422713866
result:
ok found '9.4422714', expected '9.4422714', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
2 1 1000000000
output:
0.9999999990
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
5 76 57 68 36 63
output:
63.3539651124
result:
ok found '63.3539651', expected '63.3539651', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
10 550060 445055 787034 728427 572554 894096 875473 622886 575460 119034
output:
818911.3739286328
result:
ok found '818911.3739286', expected '818911.3739286', error '0.0000000'
Test #7:
score: 0
Accepted
time: 46ms
memory: 4428kb
input:
15 10 8 9 6 9 5 3 9 7 8 7 6 7 10 7
output:
9.4986796318
result:
ok found '9.4986796', expected '9.4986796', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1807ms
memory: 20412kb
input:
20 3 2 2 1 2 3 1 3 3 2 1 2 3 2 3 2 3 1 3 1
output:
2.9999751984
result:
ok found '2.9999752', expected '2.9999752', error '0.0000000'
Test #9:
score: -100
Time Limit Exceeded
input:
21 608646711 538679781 175667175 596079164 43084965 174585378 46825084 647100103 820432909 254925688 469580725 888475497 802835182 554123188 53822453 849477025 715668397 194908968 407987651 349577139 457598738