QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#704444 | #9540. Double 11 | ucup-team4435# | WA | 1ms | 3920kb | C++20 | 2.0kb | 2024-11-02 19:59:34 | 2024-11-02 19:59:36 |
Judging History
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'