QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#67007#5170. 加速度czxb20 0ms0kbC++141.4kb2022-12-09 16:56:352022-12-09 16:56:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-09 16:56:39]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2022-12-09 16:56:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 5100;
#define IO(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout),\
	cin.tie(0)->sync_with_stdio(0), cout.tie(0)
#define F(i, a, b) for (int i = (a), iee = (b); i <= iee; i++)
#define R(i, a, b) for (int i = (a), iee = (b); i >= iee; i--)
#define diubol double
const diubol eps = 1e-6;

int n, a, s[N], l[N], r[N];

diubol f[N];

diubol vptv(diubol x, diubol t) {
	return (x - a * t * t * .5) / t;
}
diubol vpvt(diubol x, diubol v) {
	return (sqrt(v * v + 2 * a * x) - v) / a;
}

int main() {
	IO(b);
	cin >> n >> a;
	F(i, 0, n) cin >> s[i];
	F(i, 0, n) cin >> l[i] >> r[i];
	r[0] = 0;

	F(i, 1, n) f[i] = -1e18;
	diubol ans = 1e18;

	F(i, 0, n - 1) {
		{
			diubol mnv = 0, mxv = f[i];
			F(j, i + 1, n) {
				mnv = max(mnv, vptv(s[j] - s[i], r[j] - r[i]));
				mxv = min(mxv, vptv(s[j] - s[i], l[j] - r[i]));
				if (mnv > mxv + eps) break;
				if (j == n) ans = min(ans, vpvt(s[j] - s[i], mxv) + r[i]);
				assert(ans >= l[n]);
				f[j] = max(f[j], mnv + a * (s[j] - s[i]));
			}
		}
		{
			diubol mnt = r[i], mxt = 1e18;
			F(j, i + 1, n) {
				diubol T = sqrt(2. * (s[j] - s[i]) / a);
				mnt = max(mnt, l[j] - T), mxt = min(mxt, r[j] - T);
				if (mnt > mxt + eps) break;
				if (j == n) ans = min(ans, T + mnt);
				f[j] = max(f[j], T * a);
			}
		}
	}
	cout << ans << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

4 2
0 2 8 10 12
0 1000000000
2 2
4 4
6 7
6 1000000000


output:


result:


Subtask #2:

score: 0
Dangerous Syscalls

Test #7:

score: 0
Dangerous Syscalls

input:

3 20
0 4632 5697 8786
0 1000000000
1 1000000000
1 1000000000
1 1000000000

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%