QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#353175 | #958. Lockout vs tourist | HKOI0# | WA | 1ms | 4064kb | C++20 | 1.4kb | 2024-03-13 22:26:15 | 2024-03-13 22:26:16 |
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 cur_ans = 0, R = 1, U = 1e9 + 11, L = 0;
for (int j = 0; j < win.size(); j++) {
if (win[j].first >= win[j].second) {
cur_ans = win[j].first;
continue;
}
if (win[j].second < cur_ans) break;
U = min(U, win[j].second);
R -= (win[j].second - U) / (win[j].second - win[j].first); if (R < 0) break;
L += 1.0L / (win[j].second - win[j].first);
cur_ans = max(cur_ans, U - R / L);
}
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();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3868kb
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: 3828kb
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: 1ms
memory: 4064kb
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: 3736kb
input:
2 1 1000000000
output:
0.9999999990
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3748kb
input:
5 76 57 68 36 63
output:
56.9904159884
result:
wrong answer 1st numbers differ - expected: '63.3539651', found: '56.9904160', error = '0.1004444'