QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#676967#7691. B Road Bandnew_game_plus_players#WA 0ms3892kbC++141.4kb2024-10-26 06:56:562024-10-26 06:56:57

Judging History

你现在查看的是最新测评结果

  • [2024-10-26 06:56:57]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3892kb
  • [2024-10-26 06:56:56]
  • 提交

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;
}

详细

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'