QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#722493#9540. Double 11IllusionaryDominanceTL 0ms0kbC++202.0kb2024-11-07 19:14:172024-11-07 19:14:18

Judging History

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

  • [2024-11-07 19:14:18]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-11-07 19:14:17]
  • 提交

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

output:


result: