Submission #2549937
Source Code Expand
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; void main() { immutable real INF = 1L << 59; auto N = readln.chomp.to!int; auto T = new long[](N); auto X = new long[](N); foreach (i; 0..N) { auto s = readln.split.map!(to!long); T[i] = s[0]; X[i] = s[1]; } real hi = 10^^9; real lo = 0; foreach (_; 0..100) { real mid = (hi + lo) / 2; auto dp = new Tuple!(real, real)[](N+1); foreach (i; 0..N+1) dp[i] = tuple(INF, -INF); dp[0] = tuple(0.0L, 0.0L); real prev_t = 0; real prev_x = 0; foreach (i; 0..N) { if (dp[i][0] > dp[i][1]) break; real t = T[i] - prev_t; real x = abs(X[i] - prev_x); if (x <= mid * t) { dp[i+1][0] = min(dp[i+1][0], dp[i][0] - t * mid); dp[i+1][1] = max(dp[i+1][1], dp[i][1] + t * mid); } if (dp[i][0] <= X[i] && X[i] <= dp[i][1]) { dp[i+1][0] = min(dp[i+1][0], prev_x - t * mid); dp[i+1][1] = max(dp[i+1][1], prev_x + t * mid); } } (dp[N][0] <= dp[N][1] ? hi : lo) = mid; } writefln("%.09f", hi); }
Submission Info
Submission Time | |
---|---|
Task | G - 交換法則 |
User | nebukuro09 |
Language | D (LDC 0.17.0) |
Score | 0 |
Code Size | 1433 Byte |
Status | RE |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 800 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04 |
All | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 01_random_00, 01_random_01, 01_random_02, 01_random_03, 01_random_04, 01_random_05, 01_random_06, 01_random_07, 01_random_08, 01_random_09, 02_random_large_00, 02_random_large_01, 02_random_large_02, 02_random_large_03, 02_random_large_04, 02_random_large_05, 02_random_large_06, 02_random_large_07, 02_random_large_08, 02_random_large_09, 03_maximal_00, 03_maximal_01, 03_maximal_02, 03_maximal_03, 03_maximal_04, 04_fibonacci_00, 04_fibonacci_01, 04_fibonacci_02, 04_fibonacci_03, 04_fibonacci_04, 04_fibonacci_05, 04_fibonacci_06, 04_fibonacci_07, 04_fibonacci_08, 04_fibonacci_09, 05_single_00, 05_single_01, 05_single_02, 05_single_03, 05_single_04, 05_single_05, 05_single_06, 05_single_07, 05_single_08, 05_single_09, 06_dividing_00, 06_dividing_01, 06_dividing_02, 06_dividing_03, 06_dividing_04, 06_dividing_05, 06_dividing_06, 06_dividing_07, 06_dividing_08, 06_dividing_09, 97_max_00, 97_max_01, 97_max_02, 97_max_03, 97_max_04, 97_max_05, 98_challenge_00, 98_challenge_01, 98_challenge_02, 99_handmade_00, 99_handmade_01, 99_handmade_02, 99_handmade_03, 99_handmade_04, 99_handmade_05 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | RE | 1 ms | 256 KB |
00_sample_01 | RE | 1 ms | 256 KB |
00_sample_02 | RE | 1 ms | 256 KB |
00_sample_03 | RE | 1 ms | 256 KB |
00_sample_04 | RE | 1 ms | 256 KB |
01_random_00 | RE | 1 ms | 256 KB |
01_random_01 | RE | 1 ms | 256 KB |
01_random_02 | RE | 1 ms | 256 KB |
01_random_03 | RE | 1 ms | 256 KB |
01_random_04 | RE | 1 ms | 256 KB |
01_random_05 | RE | 1 ms | 256 KB |
01_random_06 | RE | 1 ms | 256 KB |
01_random_07 | RE | 1 ms | 256 KB |
01_random_08 | RE | 1 ms | 256 KB |
01_random_09 | RE | 1 ms | 256 KB |
02_random_large_00 | RE | 1 ms | 256 KB |
02_random_large_01 | RE | 1 ms | 256 KB |
02_random_large_02 | RE | 1 ms | 256 KB |
02_random_large_03 | RE | 1 ms | 256 KB |
02_random_large_04 | RE | 1 ms | 256 KB |
02_random_large_05 | RE | 1 ms | 256 KB |
02_random_large_06 | RE | 1 ms | 256 KB |
02_random_large_07 | RE | 1 ms | 256 KB |
02_random_large_08 | RE | 1 ms | 256 KB |
02_random_large_09 | RE | 1 ms | 256 KB |
03_maximal_00 | RE | 1 ms | 256 KB |
03_maximal_01 | RE | 1 ms | 256 KB |
03_maximal_02 | RE | 1 ms | 256 KB |
03_maximal_03 | RE | 1 ms | 256 KB |
03_maximal_04 | RE | 1 ms | 256 KB |
04_fibonacci_00 | RE | 1 ms | 256 KB |
04_fibonacci_01 | RE | 1 ms | 256 KB |
04_fibonacci_02 | RE | 1 ms | 256 KB |
04_fibonacci_03 | RE | 1 ms | 256 KB |
04_fibonacci_04 | RE | 1 ms | 256 KB |
04_fibonacci_05 | RE | 1 ms | 256 KB |
04_fibonacci_06 | RE | 1 ms | 256 KB |
04_fibonacci_07 | RE | 1 ms | 256 KB |
04_fibonacci_08 | RE | 1 ms | 256 KB |
04_fibonacci_09 | RE | 1 ms | 256 KB |
05_single_00 | RE | 1 ms | 256 KB |
05_single_01 | RE | 1 ms | 256 KB |
05_single_02 | RE | 1 ms | 256 KB |
05_single_03 | RE | 1 ms | 256 KB |
05_single_04 | RE | 1 ms | 256 KB |
05_single_05 | RE | 1 ms | 256 KB |
05_single_06 | RE | 1 ms | 256 KB |
05_single_07 | RE | 1 ms | 256 KB |
05_single_08 | RE | 1 ms | 256 KB |
05_single_09 | RE | 1 ms | 256 KB |
06_dividing_00 | RE | 1 ms | 256 KB |
06_dividing_01 | RE | 1 ms | 256 KB |
06_dividing_02 | RE | 1 ms | 256 KB |
06_dividing_03 | RE | 1 ms | 256 KB |
06_dividing_04 | RE | 1 ms | 256 KB |
06_dividing_05 | RE | 1 ms | 256 KB |
06_dividing_06 | RE | 1 ms | 256 KB |
06_dividing_07 | RE | 1 ms | 256 KB |
06_dividing_08 | RE | 1 ms | 256 KB |
06_dividing_09 | RE | 1 ms | 256 KB |
97_max_00 | RE | 1 ms | 256 KB |
97_max_01 | RE | 1 ms | 256 KB |
97_max_02 | RE | 1 ms | 256 KB |
97_max_03 | RE | 1 ms | 256 KB |
97_max_04 | RE | 1 ms | 256 KB |
97_max_05 | RE | 1 ms | 256 KB |
98_challenge_00 | RE | 1 ms | 256 KB |
98_challenge_01 | RE | 1 ms | 256 KB |
98_challenge_02 | RE | 1 ms | 256 KB |
99_handmade_00 | RE | 1 ms | 256 KB |
99_handmade_01 | RE | 1 ms | 256 KB |
99_handmade_02 | RE | 1 ms | 256 KB |
99_handmade_03 | RE | 1 ms | 256 KB |
99_handmade_04 | RE | 1 ms | 256 KB |
99_handmade_05 | RE | 1 ms | 256 KB |