QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#704444#9540. Double 11ucup-team4435#WA 1ms3920kbC++202.0kb2024-11-02 19:59:342024-11-02 19:59:36

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 19:59:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3920kb
  • [2024-11-02 19:59:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

#define all(a) begin(a), end(a)
#define len(a) int((a).size())

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed << setprecision(15);

    int n, m;
    cin >> n >> m;
    vector<ll> s(n);
    for (auto &x : s) {
        cin >> x;
    }
    sort(all(s));

    vector<ll> psum(n + 1);
    for (int i = 0; i < n; i++) {
        psum[i + 1] = psum[i] + s[i];
    }

    vector<pair<int, int>> segs(m);
    for (int i = 0; i < m; i++) {
        segs[i] = {i, i};
    }
    segs.back().second = n - 1;

    auto eval = [&](pair<int, int> seg) {
        return sqrtl((psum[seg.second + 1] - psum[seg.first]) * (seg.second - seg.first + 1));
    };

    priority_queue<tuple<ld, int, int>> pq;

    auto get = [&](int i, int d) -> ld {
        ld now = eval(segs[i]) + eval(segs[i + 1]);
        if (segs[i].second + d >= segs[i].first && segs[i + 1].first + d <= segs[i + 1].second) {
            ld then = eval({segs[i].first, segs[i].second + d}) + eval({segs[i + 1].first + d, segs[i + 1].second});
            if (now - then < 1e-9) {
                return -1e18;
            }
            return now - then;
        }
        return -1e18;
    };

    auto push = [&](int i) {
        if (i < 0 || i + 1 >= m) {
            return;
        }
        pq.emplace(get(i, -1), i, -1);
        pq.emplace(get(i, 1), i, 1);
    };

    for (int i = 0; i + 1 < m; i++) {
        push(i);
    }

    while (!pq.empty()) {
        auto [delta, i, d] = pq.top();
        pq.pop();
        if (delta < 1e-9) {
            break;
        }
        if (fabs(delta - get(i, d)) > 1e-8) {
            continue;
        }

        segs[i].second += d;
        segs[i + 1].first += d;
        push(i - 1);
        push(i);
        push(i + 1);
    }

    ld ans = 0;
    for (auto s : segs) {
        ans += eval(s);
    }
    cout << ans << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3920kb

input:

4 2
1 2 3 4

output:

6.191147129557119

result:

ok found '6.191147130', expected '6.191147130', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

10 3
1 2 3 4 5 6 7 8 9 10

output:

22.591625366514129

result:

ok found '22.591625367', expected '22.591625367', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

1 1
1

output:

1.000000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #4:

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

input:

1 1
100000

output:

316.227766016837933

result:

ok found '316.227766017', expected '316.227766017', error '0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

7 1
10 47 53 9 83 33 15

output:

41.833001326703777

result:

ok found '41.833001327', expected '41.833001327', error '0.000000000'

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 3832kb

input:

8 5
138 1702 119 1931 418 1170 840 1794

output:

234.101592384777177

result:

wrong answer 1st numbers differ - expected: '233.9016546', found: '234.1015924', error = '0.0008548'