QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#727942 | #5978. Runaway Quail | TrueFalse | 0 | 0ms | 0kb | C++14 | 2.0kb | 2024-11-09 14:13:32 | 2024-11-09 14:13:33 |
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...