QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#727942#5978. Runaway QuailTrueFalse0 0ms0kbC++142.0kb2024-11-09 14:13:322024-11-09 14:13:33

Judging History

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

  • [2024-11-09 14:13:33]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-09 14:13:32]
  • 提交

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() {
	freopen("tiii.in", "r", stdin);
	freopen("tiii.out", "w", stdout);

	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
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

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:


result:


Subtask #2:

score: 0
Dangerous Syscalls

Test #2:

score: 0
Dangerous Syscalls

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:


result: