QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#353187#958. Lockout vs touristHKOI0#WA 924ms36596kbC++201.5kb2024-03-13 22:42:542024-03-13 22:42:55

Judging History

This is the latest submission verdict.

  • [2024-03-13 22:42:55]
  • Judged
  • Verdict: WA
  • Time: 924ms
  • Memory: 36596kb
  • [2024-03-13 22:42:54]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

typedef 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 - 1e-12) {
                continue;
            }
            if (win[j].second < cur_ans) break;
            LD diff = U - min(U, win[j].second);
            U = min(U, win[j].second);
            R -= diff * L;
            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);
        }
        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();
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3748kb

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: 3856kb

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: 3808kb

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: 3956kb

input:

2
1 1000000000

output:

0.9999999990

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3740kb

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: 1ms
memory: 3760kb

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: 6ms
memory: 4056kb

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: 196ms
memory: 12020kb

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: 0
Accepted
time: 438ms
memory: 20184kb

input:

21
608646711 538679781 175667175 596079164 43084965 174585378 46825084 647100103 820432909 254925688 469580725 888475497 802835182 554123188 53822453 849477025 715668397 194908968 407987651 349577139 457598738

output:

831669480.2821692228

result:

ok found '831669480.2821692', expected '831669480.2821692', error '0.0000000'

Test #10:

score: 0
Accepted
time: 924ms
memory: 36512kb

input:

22
593316975 268451765 664075355 817013319 325389147 553878522 663160635 289932897 995002446 771863307 252061346 171723220 102306933 722521207 52895206 996540774 335816175 415049181 629862034 371890996 327908946 357122932

output:

899795716.3481485844

result:

ok found '899795716.3481486', expected '899795716.3481486', error '0.0000000'

Test #11:

score: 0
Accepted
time: 752ms
memory: 36580kb

input:

22
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152

output:

895851.5340571189

result:

ok found '895851.5340571', expected '895851.5340571', error '0.0000000'

Test #12:

score: 0
Accepted
time: 772ms
memory: 36596kb

input:

22
1000001 1000002 1000003 1000004 1000005 1000006 1000007 1000008 1000009 1000010 1000011 1000012 1000013 1000014 1000015 1000016 1000017 1000018 1000019 1000020 1000021 1000022

output:

1000020.4421252878

result:

ok found '1000020.4421253', expected '1000020.4421253', error '0.0000000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3808kb

input:

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

output:

999999724.4268077612

result:

ok found '999999724.4268078', expected '999999724.4268078', error '0.0000000'

Test #14:

score: -100
Wrong Answer
time: 833ms
memory: 36584kb

input:

22
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

output:

997835497.8354978561

result:

wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '997835497.8354979', error = '0.0021645'