QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#722430 | #9540. Double 11 | IllusionaryDominance | TL | 1ms | 8072kb | C++20 | 1.8kb | 2024-11-07 19:00:45 | 2024-11-07 19:00:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 200000 + 5;
int N, M, a[MAX_N], g[MAX_N], ql[MAX_N], qr[MAX_N];
ll sum[MAX_N];
double f[MAX_N];
inline double w(int i, int j) {
return sqrt((sum[j] - sum[i]) * (j - i)) + f[i];
}
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 ++;
f[i] = w(q[hd], i) + pen;
g[i] = g[q[hd]] + 1;
// fprintf(stderr, "i = %d, hd = %d, tl = %d, j = %d, g = %d, %d\n", i, hd, tl, q[hd], g[i], g[q[hd]]);
while (hd <= tl && w(i, ql[q[tl]]) <= w(q[hd], ql[q[tl]])) tl --;
if (tl < hd) {
q[++ tl] = i;
ql[i] = i + 1;
qr[i] = N;
}else if (w(q[tl], qr[q[tl]]) < w(i, qr[q[tl]])) {
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 (w(i, mid) < w(q[tl], mid)) 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 = 1e18;
while (r - l > 1e-15) {
double mid = (l + r) / 2;
dp(mid);
if (g[N] <= M) r = mid;
else l = mid;
}
dp(r);
printf("%.15lf\n", f[N] - g[N] * r);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5952kb
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: 8012kb
input:
10 3 1 2 3 4 5 6 7 8 9 10
output:
22.591625366514126
result:
ok found '22.591625367', expected '22.591625367', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5952kb
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: 5964kb
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: 8072kb
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: 7952kb
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: -100
Time Limit Exceeded
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