QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#544355#7691. B Road BandASnownWA 308ms34884kbC++141.1kb2024-09-02 15:31:042024-09-02 15:31:05

Judging History

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

  • [2024-09-02 15:31:05]
  • 评测
  • 测评结果:WA
  • 用时:308ms
  • 内存:34884kb
  • [2024-09-02 15:31:04]
  • 提交

answer

#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) x.begin(),x.end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popcount(x) (__builtin_popcount((x)))
using namespace std;
using ll=long long;
using uint=uint32_t;
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
const int N = 2e3+23;
int n,m,k,l;
double x[N],f[N][N],s[N],S[N];
signed main() {
#ifndef ONLINE_JUDGE
#endif
   cin.tie(nullptr)->sync_with_stdio(false);
   Solve();
}
void Solve() {
   cin>>n>>m>>k>>l; n+=m;
   for(int i=1;i<=n;i++) cin>>x[i];
   sort(x+1,x+n+1);
   for(int i=0;i<=n;i++) for(int j=0;j<=k;j++) 
      f[i][j]=1e9;
   for(int i=1;i<=n;i++) s[i]=s[i-1]+x[i],S[i]=S[i-1]+x[i]*x[i];
   f[0][0]=0;
   for(int i=1;i<=n;i++) for(int j=1;j<=k;j++)
      for(int k=0;k<i;k++) Min(f[i][j],f[k][j-1]+S[i]-S[k]-(s[i]-s[k])*(s[i]-s[k])/(i-k));
   printf("%.10lf\n",f[n][k]+n*l*l/4);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

18.8666666667

result:

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

Test #2:

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

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

result:

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

Test #3:

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

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

result:

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

Test #4:

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

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

result:

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

Test #5:

score: 0
Accepted
time: 153ms
memory: 33372kb

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

result:

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

Test #6:

score: 0
Accepted
time: 308ms
memory: 34884kb

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

result:

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

Test #7:

score: 0
Accepted
time: 71ms
memory: 20572kb

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

result:

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

Test #8:

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

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

result:

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

Test #9:

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

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

result:

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

Test #10:

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

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

result:

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

Test #11:

score: 0
Accepted
time: 104ms
memory: 24596kb

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:

697092.3544596303

result:

ok found '697092.35446', expected '697092.85446', error '0.00000'

Test #12:

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

input:

1 1 1 50
0
0

output:

1250.0000000000

result:

ok found '1250.00000', expected '1250.00000', error '0.00000'

Test #13:

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

input:

1 1 1 50
0
1000

output:

501250.0000000000

result:

ok found '501250.00000', expected '501250.00000', error '0.00000'

Test #14:

score: -100
Wrong Answer
time: 72ms
memory: 20452kb

input:

1 1000 99 1
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

8703.6363636255

result:

wrong answer 1st numbers differ - expected: '8703.88636', found: '8703.63636', error = '0.00003'