QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#418746#7691. B Road Bandhaze#WA 320ms39036kbC++232.0kb2024-05-23 15:30:212024-05-23 15:30:22

Judging History

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

  • [2024-05-23 15:30:22]
  • 评测
  • 测评结果:WA
  • 用时:320ms
  • 内存:39036kb
  • [2024-05-23 15:30:21]
  • 提交

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 double

LD f[2234][2234];

LD pre[2234], sqpre[2234];

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

//    cerr << s;
//    ans = (n + m) * (s / 2) * (s / 2);
    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 / (r - l + 1));
    };
    irep(i, 0, n){
        irep(j, 0, k){
            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;// << endl << (n) * (s / 2) * (s / 2);
}

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: 0ms
memory: 3852kb

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: 0ms
memory: 4060kb

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: 0ms
memory: 5788kb

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: 0ms
memory: 3936kb

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: 161ms
memory: 39036kb

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.859839089680

result:

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

Test #6:

score: 0
Accepted
time: 320ms
memory: 39016kb

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.579869979294

result:

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

Test #7:

score: 0
Accepted
time: 74ms
memory: 22324kb

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.499999981344

result:

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

Test #8:

score: 0
Accepted
time: 2ms
memory: 22540kb

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:

226037085.000000000000

result:

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

Test #9:

score: 0
Accepted
time: 5ms
memory: 20436kb

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.500000000000

result:

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

Test #10:

score: 0
Accepted
time: 6ms
memory: 22368kb

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.500000000000

result:

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

Test #11:

score: -100
Wrong Answer
time: 115ms
memory: 26824kb

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.354459637834

result:

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