QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#722493 | #9540. Double 11 | IllusionaryDominance | TL | 0ms | 0kb | C++20 | 2.0kb | 2024-11-07 19:14:17 | 2024-11-07 19:14:18 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 200000 + 5;
using db = long double;
int N, M, a[MAX_N], g[MAX_N], ql[MAX_N], qr[MAX_N];
ll sum[MAX_N];
db f[MAX_N];
db Sqrt(db qq)
{
db x = sqrt(x);
while(1)
{
db nx = (x + qq/x) / 2;
if (abs(x - nx) < 1e-9) break;
x = nx;
}
return x;
}
db w(int i, int j) {
return Sqrt((db)(sum[j] - sum[i]) * (j - i)) + f[i];
}
void dp(db pen) {
static int q[MAX_N];
int hd = 0, tl = 0;
ql[0] = 1; qr[0] = N;
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;
while (hd <= tl && w(i, ql[q[tl]]) <= w(q[hd], ql[q[tl]])) tl --, qr[q[tl]] = N;
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) >> 1;
if (w(i, mid) <= w(q[tl], mid)) r = mid - 1;
else l = mid;
}
qr[q[tl]] = l;
ql[i] = l + 1;
qr[i] = N;
q[++ tl] = i;
}
}
}
int main() {
cin >> N >> M;
for (int i = 1; i <= N ; i ++) {
cin >> a[i];
}
sort(a + 1, a + N + 1);
for (int i = 1; i <= N; i ++) {
sum[i] = sum[i - 1] + a[i];
}
db l = 0, r = 1e9;
while (r - l > 1e-15) {
db mid = (l + r) / 2;
dp(mid);
if (g[N] <= M) r = mid;
else l = mid;
}
dp(r);
cout << fixed << setprecision(10) << f[N] - g[N] * r << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
4 2 1 2 3 4