QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#727947#5978. Runaway QuailTrueFalse0 3092ms7900kbC++141.9kb2024-11-09 14:13:562024-11-09 14:13:59

Judging History

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

  • [2024-11-09 14:13:59]
  • 评测
  • 测评结果:0
  • 用时:3092ms
  • 内存:7900kb
  • [2024-11-09 14:13:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ci = const int;

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

#define il inline
#define TT template<typename T>

TT il void Max(T &x, const T &y) { if (x < y) x = y; }
TT il void Min(T &x, const T &y) { if (y < x) x = y; }

const int N = 505;

int T, C, n;
double dp[2][N][N];

struct Node {
	int x, v;
} a[N], b[N], c[N];
int n1, n2;

bool cmp(const Node &x, const Node &y) { return x.v < y.v; }

void work() {
	cin >> C >> n;
	n1 = n2 = 0;
	for (int i = 1; i <= n; ++i) cin >> c[i].x;
	for (int i = 1; i <= n; ++i) cin >> c[i].v;
	for (int i = 1; i <= n; ++i) {
		if (c[i].x < 0) a[++n1] = c[i], a[n1].x *= -1;
		else b[++n2] = c[i];
	}

	sort(a + 1, a + 1 + n1, cmp);
	sort(b + 1, b + 1 + n2, cmp);

	memset(dp, 0x77, sizeof dp);
	dp[0][0][0] = dp[1][0][0] = 0;
	for (int i = 0; i <= n1; ++i) {
		for (int j = 0; j <= n2; ++j) {
			double t0 = dp[0][i][j], t1 = dp[1][i][j];
			double pos, mx(0);
			pos = t0 * a[i].v + a[i].x;
			for (int k = i + 1; k <= n1; ++k) {
				Max(mx, t0 + max(a[k].x + a[k].v * t0 - pos, 0.0) / (C - a[k].v));
				Min(dp[0][k][j], mx);
			}
			mx = 0;
			for (int k = j + 1; k <= n2; ++k) {
				Max(mx, t0 + max(b[k].x + b[k].v * t0 + pos, 0.0) / (C - b[k].v));
				Min(dp[1][i][k], mx);
			}
			pos = t1 * b[j].v + b[j].x;
			mx = 0;
			for (int k = i + 1; k <= n1; ++k) {
				Max(mx, t1 + max(a[k].x + a[k].v * t1 + pos, 0.0) / (C - a[k].v));
				Min(dp[0][k][j], mx);
			}
			mx = 0;
			for (int k = j + 1; k <= n2; ++k) {
				Max(mx, t1 + max(b[k].x + b[k].v * t1 - pos, 0.0) / (C - b[k].v));
				Min(dp[1][i][k], mx);
			}

		}
	}
	cout << fixed << setprecision(8) << min(dp[0][n1][n2], dp[1][n1][n2]) << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> T;
	while (T--) work();

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 7900kb

input:

50
4 3
-3 -6 -9
3 2 1
2 2
1 -1
1 1
1000 25
769234 -5735820 -524288 -5403090 -6429140 1574982 1 -9733628 -1407481 4093041 4117720 -3193501 -9765195 -3069520 1122216 -5799108 131072 -8482066 -256 -8021159 -8958386 -7027036 5370579 -3602534 -6834567
425 102 744 155 339 19 999 19 159 198 51 304 369 601 ...

output:

3.00000000
5.00000000
741437.84571823
429262.39614211
659984.21764798
349748.87032843
1976794.00600961
602687.91814159
5725896.87634408
659154.05137579
787850.43477244
610881.70515970
489354.65912208
658325.97094849
656676.03626253
190325.65298332
1653744.99707602
1056722.49652778
657499.96851474
45...

result:

wrong output format Expected 'Case' but found '3.00000000' (test case 1)

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 3092ms
memory: 7892kb

input:

50
4 3
-3 -6 -9
3 2 1
2 2
1 -1
1 1
1000 500
-9650379 9806301 -6495789 -1283284 5022779 4725553 9364178 -8123302 -9609729 7847458 -142364 6983908 8147008 -3186924 7339254 -8737645 8757174 7887319 3609962 5780915 -1752801 -1657946 -9511339 5113995 -7887160 -6093170 260267 -3837106 -356098 6676924 6210...

output:

3.00000000
5.00000000
205825967.74443400
505841.22885402
1398220.96631594
13741948.49999943
1627320.23101635
1168419.68631179
657499.96851474
8058469.51612837
657499.96851474
901021.43190392
656676.03626253
511916.31332739
1642671.47375408
658325.97094849
695884.42192288
7792241109.99967766
9260690....

result:

wrong output format Expected 'Case' but found '3.00000000' (test case 1)