QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #730938 | #9540. Double 11 | IllusionaryDominance | WA | 2ms | 8152kb | C++20 | 2.2kb | 2024-11-09 22:32:24 | 2024-11-09 22:32:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <double, int> pdi;
const int MAX_N = 200000 + 5;
const double EPS = 1e-9;
int N, M, a[MAX_N], g[MAX_N], ql[MAX_N], qr[MAX_N], pre[MAX_N];
ll sum[MAX_N];
double f[MAX_N];
inline pdi w(int i, int j) {
return pair(sqrt((sum[j] - sum[i]) * (j - i)) + f[i], g[i] + 1);
}
inline bool cmp(const pdi &a, const pdi &b, const double &pen) {
double x = a.first - b.first, y = pen * (a.second - b.second);
if (abs(x + y) < EPS) return a.second < b.second;
return x + y < 0;
}
void dp(double pen) {
static int q[MAX_N];
int hd = 0, tl = 0;
ql[0] = 1; qr[0] = N; q[0] = 0;
for (int i = 1; i <= N; i ++) {
while (hd <= tl && qr[q[hd]] < i) hd ++;
if (ql[q[hd]] <= i) ql[q[hd]] = i + 1;
f[i] = w(q[hd], i).first;
g[i] = g[q[hd]] + 1;
pre[i] = q[hd];
while (hd <= tl && !cmp(w(q[hd], ql[q[tl]]), w(i, ql[q[tl]]), pen)) tl --;
if (tl < hd) {
q[++ tl] = i;
ql[i] = i + 1;
qr[i] = N;
}else if (cmp(w(q[tl], qr[q[tl]]), w(i, qr[q[tl]]), pen)) {
if (qr[q[tl]] < N) {
ql[i] = qr[q[tl]] + 1;
qr[i] = N;
q[++ tl] = i;
}
}else {
int l = ql[q[tl]], r = qr[q[tl]];
while (l < r) {
int mid = l + r >> 1;
if (!cmp(w(q[tl], mid), w(i, mid), pen)) r = mid;
else l = mid + 1;
}
qr[q[tl]] = l - 1;
ql[i] = l;
qr[i] = N;
q[++ tl] = i;
}
}
}
int main() {
scanf("%d%d", &N, &M);
for (int i = 1; i <= N ; i ++) {
scanf("%d", a + i);
}
sort(a + 1, a + N + 1);
for (int i = 1; i <= N; i ++) {
sum[i] = sum[i - 1] + a[i];
}
double l = 0, r = 1e9;
while (r - l > 1e-9) {
double mid = (l + r) / 2;
dp(mid);
if (g[N] <= M) r = mid;
else l = mid;
}
dp(r);
double ans = 0;
for (int i = N; i; i = pre[i]) {
ans += sqrt((sum[i] - sum[pre[i]]) * (i - pre[i]));
}
printf("%.15lf\n", ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 8140kb
input:
4 2 1 2 3 4
output:
6.191147129557120
result:
ok found '6.191147130', expected '6.191147130', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 8152kb
input:
10 3 1 2 3 4 5 6 7 8 9 10
output:
22.591625366514130
result:
ok found '22.591625367', expected '22.591625367', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 8008kb
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: 8028kb
input:
1 1 100000
output:
316.227766016837961
result:
ok found '316.227766017', expected '316.227766017', error '0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 8120kb
input:
7 1 10 47 53 9 83 33 15
output:
41.833001326703780
result:
ok found '41.833001327', expected '41.833001327', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 8080kb
input:
8 5 138 1702 119 1931 418 1170 840 1794
output:
233.901654551943579
result:
ok found '233.901654552', expected '233.901654552', error '0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 8032kb
input:
58 1 888 251 792 847 685 3 182 461 102 348 555 956 771 901 712 878 580 631 342 333 285 899 525 725 537 718 929 653 84 788 104 355 624 803 253 853 201 995 536 184 65 205 540 652 549 777 248 405 677 950 431 580 600 846 328 429 134 983
output:
1355.265287683559109
result:
ok found '1355.265287684', expected '1355.265287684', error '0.000000000'
Test #8:
score: -100
Wrong Answer
time: 1ms
memory: 8092kb
input:
88 30 67117 31903 93080 85196 16438 97116 11907 72959 83651 41273 52873 81892 81468 51323 99992 58869 54258 7183 87358 90990 80596 41252 90769 82705 61434 8524 13575 10787 53950 96768 12062 34637 27806 70937 69653 28380 90236 3352 27537 3873 91006 89790 25369 91825 82734 5588 4539 74118 47098 84741 ...
output:
18791.507356802183494
result:
wrong answer 1st numbers differ - expected: '18791.4753541', found: '18791.5073568', error = '0.0000017'