QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353175#958. Lockout vs touristHKOI0#WA 1ms4064kbC++201.4kb2024-03-13 22:26:152024-03-13 22:26:16

Judging History

This is the latest submission verdict.

  • [2024-03-13 22:26:16]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4064kb
  • [2024-03-13 22:26:15]
  • Submitted

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();
}

Details

Tip: Click on the bar to expand more detailed information

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'