QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#418782#7691. B Road Bandhaze#WA 1056ms77460kbC++231.9kb2024-05-23 15:42:002024-05-23 15:42:01

Judging History

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

  • [2024-05-23 15:42:01]
  • 评测
  • 测评结果:WA
  • 用时:1056ms
  • 内存:77460kb
  • [2024-05-23 15:42:00]
  • 提交

answer

/*

Author: Haze

2024/5/23

*/

#include <bits/stdc++.h>

#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;

inline ll readL() {
    ll s = 0;
    bool fl = false;
    char ch = (char) getchar();
    while (!isdigit(ch)) {
        if (ch == '-')fl = true;
        ch = (char) getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + (ch ^ 48);
        ch = (char) getchar();
    }
    return fl ? -s : s;
}

inline int read() {
    return (int) (readL());
}

const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 1000 + 7;

#define LD long double

LD f[2234][2234];

LD pre[2234], sqpre[2234];

void solve() {
    ll n = read(), m = read(), k = read();
    LD s, ans = 0;
    cin >> s;
    LD base = 1.0 * s * s * (1.0 * n * m / (1.0 * (m + n)));

    vector<LD>a(n + m + 1);

    irep(i, 0, n + m - 1){
        cin >> a[i + 1];
    }
    n = n + m;
    sort(a.begin() + 1, a.end());
    irep(i, 1, n){
        pre[i] = pre[i - 1] + a[i];
        sqpre[i] = sqpre[i - 1] + a[i] * a[i];
    }

    auto w = [&](int l, int r){
        return sqpre[r] - sqpre[l - 1] - (pre[r] - pre[l - 1]) * (pre[r] - pre[l - 1]) * (1.0 / (1.0 * r - l + 1));
    };
    irep(i, 0, 2050){
        irep(j, 0, 2050){
            f[i][j] = llinf;
        }
    }
    f[0][0] = 0;
    irep(i, 0, n - 1){
        irep(j, 0, k - 1){
            irep(ii, i + 1, n){
                f[ii][j + 1] = min(f[ii][j + 1], f[i][j] + w(i + 1, ii));
            }
        }
    }
    ans = f[n][1];
    irep(j, 0, k){
        ans = min(ans, f[n][j]);
    }
    cout << fixed << setprecision(12) << ans + base;
}

int main() {
    // IOS
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 16ms
memory: 75556kb

input:

4 4 2 3
0.5 1.0 3.0 3.5
1.0 2.5 3.0 3.5

output:

18.866666666667

result:

ok found '18.86667', expected '18.86667', error '0.00000'

Test #2:

score: 0
Accepted
time: 11ms
memory: 77364kb

input:

9 9 3 2
1 2 3 5 6 7 9 10 11
1 2 3 5 6 7 9 10 11

output:

30.000000000000

result:

ok found '30.00000', expected '30.00000', error '0.00000'

Test #3:

score: 0
Accepted
time: 3ms
memory: 77324kb

input:

9 9 2 2
1 2 3 5 6 7 9 10 11
1 2 3 5 6 7 9 10 11

output:

69.900000000000

result:

ok found '69.90000', expected '69.90000', error '0.00000'

Test #4:

score: 0
Accepted
time: 7ms
memory: 75676kb

input:

9 9 4 2
1 2 3 5 6 7 9 10 11
1 2 3 5 6 7 9 10 11

output:

27.000000000000

result:

ok found '27.00000', expected '27.00000', error '0.00000'

Test #5:

score: 0
Accepted
time: 537ms
memory: 77012kb

input:

1000 1000 50 50
330.73 339.71 953.72 23.16 638.53 63.45 962.76 333.8 598.13 217.16 515.65 61.91 700.25 674.76 623.15 664.65 721.77 286.49 69.91 880.07 547.7 433.38 384.93 802.7 130.46 874.74 285.52 280.83 764.82 528.59 978.47 4.95 325.9 183.52 748.54 867.48 434.04 730.72 439.99 918.07 426.39 868.28 ...

output:

1308206.859840847479

result:

ok found '1308206.85984', expected '1308206.85984', error '0.00000'

Test #6:

score: 0
Accepted
time: 1056ms
memory: 77304kb

input:

1000 1000 100 50
105.67 449.24 806.29 311.9 769.96 429.75 615.75 129.89 341.97 740.16 810.73 230.26 544.63 99.66 232.57 733.62 741.15 707.48 364.11 223.4 961.2 997.79 885.57 389.15 529.83 615.18 377.93 919.18 999.44 653.69 817.85 774.44 173.74 744.18 721.5 422.42 866.58 585.33 717.53 122.96 511.1 70...

output:

1263688.579870550108

result:

ok found '1263688.57987', expected '1263688.57987', error '0.00000'

Test #7:

score: 0
Accepted
time: 268ms
memory: 77460kb

input:

500 500 100 25
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 6.0 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 7.0 7...

output:

156332.499999973583

result:

ok found '156332.50000', expected '156332.50000', error '0.00000'

Test #8:

score: 0
Accepted
time: 4ms
memory: 76316kb

input:

500 500 1 25
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 6.0 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 7.0 7.1...

output:

226037084.999999994790

result:

ok found '226037085.00000', expected '226037085.00000', error '0.00000'

Test #9:

score: 0
Accepted
time: 10ms
memory: 76512kb

input:

500 500 2 25
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 6.0 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 7.0 7.1...

output:

364582.499999990098

result:

ok found '364582.50000', expected '364582.50000', error '0.00000'

Test #10:

score: 0
Accepted
time: 19ms
memory: 76168kb

input:

500 500 3 25
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 6.0 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 7.0 7.1...

output:

286457.499999990097

result:

ok found '286457.50000', expected '286457.50000', error '0.00000'

Test #11:

score: -100
Wrong Answer
time: 398ms
memory: 77164kb

input:

250 1000 97 47
11.51 12.23 12.91 13.73 14.51 15.11 15.83 16.57 17.33 18.11 18.89 19.87 20.53 21.29 22.13 22.87 23.57 24.23 25.31 26.17 26.87 27.41 28.19 29.03 29.99 30.79 31.81 32.57 33.31 34.13 35.11 35.71 36.43 37.27 38.21 39.07 39.89 40.57 41.39 42.31 42.97 44.09 44.93 45.83 46.57 47.51 48.31 49....

output:

448580.354459823504

result:

wrong answer 1st numbers differ - expected: '697092.85446', found: '448580.35446', error = '0.35650'