QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107773#5387. iCarPetroTarnavskyiWA 13ms3772kbC++172.4kb2023-05-22 19:47:452023-05-22 19:47:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-22 19:47:48]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:3772kb
  • [2023-05-22 19:47:45]
  • 提交

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;
}

详细

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'