QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#733055#5978. Runaway QuailXSC0620 0ms0kbC++142.1kb2024-11-10 16:58:312024-11-10 16:58:33

Judging History

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

  • [2024-11-10 16:58:33]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-10 16:58:31]
  • 提交

answer

#include <bits/stdc++.h>
const double eps = 1e-10;
int main() {
#ifdef ONLINE_JUDGE
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	std::freopen("tiii.in", "r", stdin);
	std::freopen("tiii.out", "w", stdout);
#else
	std::freopen(".in", "r", stdin);
	std::freopen(".out", "w", stdout);
#endif
	int T;
	for (std::cin >> T; T--; ) {
		int v, n;
		std::cin >> v >> n;
		std::vector<std::pair<int, int> > a(n + 1);
		for (int i = 1; i <= n; ++i)
			std::cin >> a[i].first;
		for (int i = 1; i <= n; ++i)
			std::cin >> a[i].second;
		a.emplace_back(0, 0), ++n;
		std::sort(a.begin() + 1, a.end());
		int p = std::lower_bound(a.begin() + 1, a.end(), std::make_pair(0, 0)) - a.begin();
		std::sort(a.begin() + 1, a.begin() + p, [](std::pair<int, int> x, std::pair<int, int> y) { return x.second < y.second; });
		std::sort(a.begin() + p + 1, a.end(), [](std::pair<int, int> x, std::pair<int, int> y) { return x.second > y.second; });
		std::vector<std::vector<double> > f(n + 1, std::vector<double> (n + 1, 1e18));
		f[1][n] = 0.;
		auto at = [&](int i, double t) {
			return std::fabs(a[i].first + t * a[i].second * (i < p ? -1 : 1));
		};
		auto calc = [&](int i, double t) {
			return at(i, t) / (v - a[i].second);
		};
		// for (int i = 1; i <= n; ++i)
		// 	printf("%d: (%d, %d)\n", i, a[i].first, a[i].second);
		for (int i = 1; i <= p; ++i)
			for (int j = n; j >= p; --j) {
				if (i == p && j == p)
					break;
				double d = 0.;
				// printf("[%d, %d]: %lf\n", i, j, f[i][j]);
				for (int k = i; k < p; ++k) {
					if (at(k, f[i][j]) >= at(i, f[i][j]) - eps)
						d = std::max(d, calc(k, f[i][j]));
					// printf("  k1 = %d, d = %lf\n", k, d);
					f[k + 1][j] = std::min(f[k + 1][j], f[i][j] + d + (k != j - 1) * d);
				}
				d = 0.;
				for (int k = j; k > p; --k) {
					if (at(k, f[i][j]) >= at(j, f[i][j]) - eps)
						d = std::max(d, calc(k, f[i][j]));
					// printf("  k2 = %d, d = %lf\n", k, d);
					f[i][k - 1] = std::min(f[i][k - 1], f[i][j] + d + (k != i + 1) * d);
				}
			}
		std::cout << std::fixed << std::setprecision(7) << f[p][p] << '\n';
	}
	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: