QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#418746 | #7691. B Road Band | haze# | WA | 320ms | 39036kb | C++23 | 2.0kb | 2024-05-23 15:30:21 | 2024-05-23 15:30:22 |
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 double
LD f[2234][2234];
LD pre[2234], sqpre[2234];
void solve() {
int n = read(), m = read(), k = read();//s = read();
LD s, ans = 0;
cin >> s;
LD base = 1.0 * s * s * (n * m / (1.0 * (m + n)));
// cerr << base;
// cerr << s;
// ans = (n + m) * (s / 2) * (s / 2);
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 / (r - l + 1));
};
irep(i, 0, n){
irep(j, 0, k){
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;// << endl << (n) * (s / 2) * (s / 2);
}
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: 0ms
memory: 3852kb
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: 0ms
memory: 4060kb
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: 0ms
memory: 5788kb
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: 0ms
memory: 3936kb
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: 161ms
memory: 39036kb
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.859839089680
result:
ok found '1308206.85984', expected '1308206.85984', error '0.00000'
Test #6:
score: 0
Accepted
time: 320ms
memory: 39016kb
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.579869979294
result:
ok found '1263688.57987', expected '1263688.57987', error '0.00000'
Test #7:
score: 0
Accepted
time: 74ms
memory: 22324kb
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.499999981344
result:
ok found '156332.50000', expected '156332.50000', error '0.00000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 22540kb
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.000000000000
result:
ok found '226037085.00000', expected '226037085.00000', error '0.00000'
Test #9:
score: 0
Accepted
time: 5ms
memory: 20436kb
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.500000000000
result:
ok found '364582.50000', expected '364582.50000', error '0.00000'
Test #10:
score: 0
Accepted
time: 6ms
memory: 22368kb
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.500000000000
result:
ok found '286457.50000', expected '286457.50000', error '0.00000'
Test #11:
score: -100
Wrong Answer
time: 115ms
memory: 26824kb
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.354459637834
result:
wrong answer 1st numbers differ - expected: '697092.85446', found: '448580.35446', error = '0.35650'