QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#676967 | #7691. B Road Band | new_game_plus_players# | WA | 0ms | 3892kb | C++14 | 1.4kb | 2024-10-26 06:56:56 | 2024-10-26 06:56:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
typedef long long ll;
int n, m, k, c;
double a[MAXN], s[MAXN][2];
double dp[MAXN], nxt[MAXN];
double cost(int l, int r) {
if (l > r) return 0;
double s0 = r - l + 1;
double s1 = s[r][0] - s[l - 1][0];
double s2 = s[r][1] - s[l - 1][1];
double x = s1 / s0;
return s2 - s1 * x * 2 + s0 * x * x;
}
void work(int l, int r, int ql, int qr) {
int mid = (l + r) / 2, pos = -1;
for (int i = ql; i <= qr; i++)
if (dp[i] + cost(i + 1, r) < nxt[mid]) {
nxt[mid] = dp[i] + cost(i + 1, r);
pos = i;
}
if (l < mid) work(l, mid - 1, ql, pos);
if (mid < r) work(mid + 1, r, pos, qr);
}
int main() {
scanf("%d%d%d%d", &n, &m, &k, &c);
for (int i = 1; i <= n; i++)
scanf("%lf", &a[i]);
for (int i = 1; i <= m; i++)
scanf("%lf", &a[n + i]);
sort(a + 1, a + n + m + 1);
for (int i = 1; i <= n + m; i++) {
s[i][0] = s[i - 1][0] + a[i];
s[i][1] = s[i - 1][1] + a[i] * a[i];
}
for (int i = 1; i <= n + m; i++)
dp[i] = cost(1, i);
for (int t = 2; t <= k; t++) {
for (int i = 1; i <= n + m; i++)
nxt[i] = 1e100;
work(1, n + m, 1, n + m);
for (int i = 1; i <= n + m; i++)
dp[i] = nxt[i];
// for (int i = n + m; i >= 1; i--)
// for (int j = 1; j <= i - 1; j++)
// dp[i] = min(dp[i], dp[j] + cost(j + 1, i));
}
printf("%.10lf\n", dp[n + m] + (n + m) * (c / 2.0) * (c / 2.0));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
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: -100
Wrong Answer
time: 0ms
memory: 3892kb
input:
9 9 3 2 1 2 3 5 6 7 9 10 11 1 2 3 5 6 7 9 10 11
output:
44.3000000000
result:
wrong answer 1st numbers differ - expected: '30.00000', found: '44.30000', error = '0.47667'