QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#727947 | #5978. Runaway Quail | TrueFalse | 0 | 3092ms | 7900kb | C++14 | 1.9kb | 2024-11-09 14:13:56 | 2024-11-09 14:13:59 |
Judging History
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)