QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243894#7691. B Road BandSolitaryDream#WA 298ms5352kbC++17816b2023-11-08 18:58:292023-11-08 18:58:30

Judging History

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

  • [2023-11-08 18:58:30]
  • 评测
  • 测评结果:WA
  • 用时:298ms
  • 内存:5352kb
  • [2023-11-08 18:58:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)t
typedef double db;
const int N=2005;
db a[N],s[N],s2[N];
db f[N][105];
int main() {
    int m,n,K,d;
    scanf("%d%d%d%d",&m,&n,&K,&d);
    db res=m*d*d-1.0*m*d*m*d/(m+n);
    // cerr << res << endl;
    n+=m;
    FOR(i,1,n) scanf("%lf",&a[i]);
    sort(a+1,a+n+1);
    FOR(i,1,n) {
        s[i]=s[i-1]+a[i];
        s2[i]=s2[i-1]+a[i]*a[i];
    }
    FOR(i,1,n) {
        f[i][0]=1e18;
        FOR(k,1,K) {
            f[i][k]=1e18;
            FOR(j,0,i-1) {
                f[i][k]=min(f[i][k],f[j][k-1]+s2[i]-s2[j]-(s[i]-s[j])*(s[i]-s[j])/(i-j));
            }
        }
    }
    printf("%.9lf\n",f[n][K]+res);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3676kb

input:

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

output:

18.866666667

result:

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

Test #2:

score: 0
Accepted
time: 1ms
memory: 3804kb

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

result:

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

Test #3:

score: 0
Accepted
time: 1ms
memory: 3816kb

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

result:

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

Test #4:

score: 0
Accepted
time: 1ms
memory: 3804kb

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

result:

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

Test #5:

score: 0
Accepted
time: 147ms
memory: 5252kb

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

result:

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

Test #6:

score: 0
Accepted
time: 298ms
memory: 5352kb

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

result:

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

Test #7:

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

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

result:

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

Test #8:

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

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

result:

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

Test #9:

score: 0
Accepted
time: 0ms
memory: 4500kb

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

result:

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

Test #10:

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

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

result:

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

Test #11:

score: -100
Wrong Answer
time: 110ms
memory: 4776kb

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

result:

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