QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#418782 | #7691. B Road Band | haze# | WA | 1056ms | 77460kb | C++23 | 1.9kb | 2024-05-23 15:42:00 | 2024-05-23 15:42:01 |
Judging History
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 long double
LD f[2234][2234];
LD pre[2234], sqpre[2234];
void solve() {
ll n = read(), m = read(), k = read();
LD s, ans = 0;
cin >> s;
LD base = 1.0 * s * s * (1.0 * n * m / (1.0 * (m + n)));
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 / (1.0 * r - l + 1));
};
irep(i, 0, 2050){
irep(j, 0, 2050){
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;
}
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: 16ms
memory: 75556kb
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: 11ms
memory: 77364kb
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: 3ms
memory: 77324kb
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: 7ms
memory: 75676kb
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: 537ms
memory: 77012kb
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.859840847479
result:
ok found '1308206.85984', expected '1308206.85984', error '0.00000'
Test #6:
score: 0
Accepted
time: 1056ms
memory: 77304kb
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.579870550108
result:
ok found '1263688.57987', expected '1263688.57987', error '0.00000'
Test #7:
score: 0
Accepted
time: 268ms
memory: 77460kb
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.499999973583
result:
ok found '156332.50000', expected '156332.50000', error '0.00000'
Test #8:
score: 0
Accepted
time: 4ms
memory: 76316kb
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:
226037084.999999994790
result:
ok found '226037085.00000', expected '226037085.00000', error '0.00000'
Test #9:
score: 0
Accepted
time: 10ms
memory: 76512kb
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.499999990098
result:
ok found '364582.50000', expected '364582.50000', error '0.00000'
Test #10:
score: 0
Accepted
time: 19ms
memory: 76168kb
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.499999990097
result:
ok found '286457.50000', expected '286457.50000', error '0.00000'
Test #11:
score: -100
Wrong Answer
time: 398ms
memory: 77164kb
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.354459823504
result:
wrong answer 1st numbers differ - expected: '697092.85446', found: '448580.35446', error = '0.35650'