QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#733057 | #5978. Runaway Quail | XSC062 | 0 | 1458ms | 5492kb | C++14 | 2.1kb | 2024-11-10 16:58:46 | 2024-11-10 16:58:46 |
Judging History
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);
#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
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3784kb
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.0000000 5.0000000 741808.6795580 429262.3961421 20882.3778338 349923.7066818 1977782.8269231 378516.6937152 487735.4241918 20856.1106918 788244.4925187 597687.2622650 489599.3923182 20829.9095477 20777.7042607 196692.3226842 1654572.2046784 1057251.0555556 20803.7741531 250762.3067432 102916.31523...
result:
wrong output format Expected 'Case' but found '3.0000000' (test case 1)
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 0
Wrong Answer
time: 1458ms
memory: 5492kb
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.0000000 5.0000000 205911250.0888889 506094.2114598 1398920.3479899 5003649.4018036 1597454.5521669 1169004.1178707 20803.7741531 4013012.0146146 20803.7741531 901472.0734406 20777.7042607 17292.4410923 1643493.1258170 20829.9095477 696232.4596527 7792241110.0000000 6673569.8173884 2853075.2739883 ...
result:
wrong output format Expected 'Case' but found '3.0000000' (test case 1)