QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243894 | #7691. B Road Band | SolitaryDream# | WA | 298ms | 5352kb | C++17 | 816b | 2023-11-08 18:58:29 | 2023-11-08 18:58:30 |
Judging History
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'