QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107773 | #5387. iCar | PetroTarnavskyi | WA | 13ms | 3772kb | C++17 | 2.4kb | 2023-05-22 19:47:45 | 2023-05-22 19:47:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef double db;
const int N = 17;
const int MAGIC = 74;
void updMax(db& x, db val) {
x = max(x, val);
}
db solve(db a, db b, db c, db l, db r) {
db D = b * b - 4 * a * c;
D = sqrt(max(0.0, D));
D *= -1;
FOR(it, 0, 2) {
db t = (-b + D) / 2;
D *= -1;
if (t < l || t > r) {
continue;
}
return t;
}
return 1e47;
assert(false);
}
db dp[N][MAGIC];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> T(n), g(n), r(n);
FOR(i, 1, n) {
cin >> T[i] >> g[i] >> r[i];
}
FOR(i, 0, n) {
FOR(j, 0, MAGIC) {
dp[i][j] = -1e47;
}
}
db ans = 1e9;
dp[0][0] = 0;
FOR(i1, 0, n) {
int y1 = i1 * 1000;
FOR(j1, 0, MAGIC) {
db v = dp[i1][j1];
if (v < -1) {
continue;
}
int tau1 = T[i1] + j1 * (g[i1] + r[i1]);
FOR(i2, i1 + 1, n) {
int y2 = i2 * 1000;
FOR(j2, 0, MAGIC) {
int tau2 = T[i2] + j2 * (g[i2] + r[i2]);
if (tau1 > tau2) {
continue;
}
db b = v - (tau1 + tau2), c = (tau1 * tau1 + tau2 * tau2) / 2.0 - v * tau1 + y1 - y2;
db t = solve(1, b, c, tau1, tau2);
db x = y2 - (tau2 - t) * (tau2 - t) / 2;
bool ok = true;
FOR(i, i1 + 1, i2) {
int y = i * 1000, ty;
if (y < x) {
ty = solve(1, 2 * (v - tau1), tau1 * tau1 - 2 * v * tau1 - 2 * (y - y1), tau1, tau2);
}
else {
ty = sqrt(2 * (y - x)) + t;
}
if((ty - T[i] + g[i] + r[i]) % (g[i] + r[i]) >= g[i])
ok = 0;
}
if (ok) {
updMax(dp[i2][j2], tau2 - t);
}
}
}
db x = n * 1000;
db t = solve(1, 2 * (v - tau1), tau1 * tau1 - 2 * v * tau1 - 2 * (x - y1), tau1, 1e9);
bool ok = 1;
FOR(i, i1 + 1, n){
db y = i * 1000;
int ty = solve(1, 2 * (v - tau1), tau1 * tau1 - 2 * v * tau1 - 2 * (y - y1), tau1, 1e9);
if((ty - T[i] + g[i] + r[i]) % (g[i] + r[i]) >= g[i])
ok = 0;
}
if(ok) {
ans = min(ans, t);
}
}
}
cout << fixed << setprecision(10) << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 13ms
memory: 3772kb
input:
16 37 40 43 21 43 48 84 46 49 53 40 47 40 43 41 68 41 46 71 49 40 87 50 44 9 40 43 38 43 47 19 47 42 68 44 48 71 45 46 79 40 42 68 45 41
output:
511.4230502556
result:
wrong answer 1st numbers differ - expected: '355.9979364', found: '511.4230503', error = '0.4365899'