QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#544355 | #7691. B Road Band | ASnown | WA | 308ms | 34884kb | C++14 | 1.1kb | 2024-09-02 15:31:04 | 2024-09-02 15:31:05 |
Judging History
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'