Submission #2549944
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 | F - ダブルス |
User | nebukuro09 |
Language | D (LDC 0.17.0) |
Score | 0 |
Code Size | 1433 Byte |
Status | WA |
Exec Time | 434 ms |
Memory | 20988 KB |
Judge Result
Set Name | Sample | Small | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 600 | 0 / 200 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04 |
Small | 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_X_positive_00, 02_X_positive_01, 02_X_positive_02, 02_X_positive_03, 02_X_positive_04, 03_X_negative_00, 03_X_negative_01, 03_X_negative_02, 03_X_negative_03, 03_X_negative_04, 04_T_large_00, 04_T_large_01, 04_T_large_02, 04_T_large_03, 04_T_large_04, 04_T_small_00, 04_T_small_01, 04_T_small_02, 04_T_small_03, 04_T_small_04, 05_X_negative_large_00, 05_X_negative_large_01, 05_X_negative_large_02, 05_X_negative_large_03, 05_X_negative_large_04, 05_X_positive_large_00, 05_X_positive_large_01, 05_X_positive_large_02, 05_X_positive_large_03, 05_X_positive_large_04, 05_absX_large_00, 05_absX_large_01, 05_absX_large_02, 05_absX_large_03, 05_absX_large_04, 05_absX_small_00, 05_absX_small_01, 05_absX_small_02, 05_absX_small_03, 05_absX_small_04, 08_V_minimum_nonzero_00, 09_max_00, 09_max_01, 09_max_02, 09_max_03, 09_max_04, 09_max_05, 09_max_06, 09_max_07, 09_max_08, 09_max_09, 09_max_10, 09_max_11, 09_max_12 |
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_X_positive_00, 02_X_positive_01, 02_X_positive_02, 02_X_positive_03, 02_X_positive_04, 03_X_negative_00, 03_X_negative_01, 03_X_negative_02, 03_X_negative_03, 03_X_negative_04, 04_T_large_00, 04_T_large_01, 04_T_large_02, 04_T_large_03, 04_T_large_04, 04_T_small_00, 04_T_small_01, 04_T_small_02, 04_T_small_03, 04_T_small_04, 05_X_negative_large_00, 05_X_negative_large_01, 05_X_negative_large_02, 05_X_negative_large_03, 05_X_negative_large_04, 05_X_positive_large_00, 05_X_positive_large_01, 05_X_positive_large_02, 05_X_positive_large_03, 05_X_positive_large_04, 05_absX_large_00, 05_absX_large_01, 05_absX_large_02, 05_absX_large_03, 05_absX_large_04, 05_absX_small_00, 05_absX_small_01, 05_absX_small_02, 05_absX_small_03, 05_absX_small_04, 08_V_minimum_nonzero_00, 09_max_00, 09_max_01, 09_max_02, 09_max_03, 09_max_04, 09_max_05, 09_max_06, 09_max_07, 09_max_08, 09_max_09, 09_max_10, 09_max_11, 09_max_12, 11_random_00, 11_random_01, 11_random_02, 11_random_03, 11_random_04, 11_random_05, 11_random_06, 11_random_07, 11_random_08, 11_random_09, 12_X_positive_00, 12_X_positive_01, 12_X_positive_02, 12_X_positive_03, 12_X_positive_04, 13_X_negative_00, 13_X_negative_01, 13_X_negative_02, 13_X_negative_03, 13_X_negative_04, 14_T_large_00, 14_T_large_01, 14_T_large_02, 14_T_large_03, 14_T_large_04, 14_T_small_00, 14_T_small_01, 14_T_small_02, 14_T_small_03, 14_T_small_04, 15_X_negative_large_00, 15_X_negative_large_01, 15_X_negative_large_02, 15_X_negative_large_03, 15_X_negative_large_04, 15_X_positive_large_00, 15_X_positive_large_01, 15_X_positive_large_02, 15_X_positive_large_03, 15_X_positive_large_04, 15_absX_large_00, 15_absX_large_01, 15_absX_large_02, 15_absX_large_03, 15_absX_large_04, 15_absX_small_00, 15_absX_small_01, 15_absX_small_02, 15_absX_small_03, 15_absX_small_04, 19_max_00, 19_max_01, 19_max_02, 19_max_03, 19_max_04, 19_max_05, 19_max_06, 19_max_07, 19_max_08, 19_max_09, 19_max_10, 19_max_11, 19_max_12 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | AC | 1 ms | 256 KB |
00_sample_01 | AC | 1 ms | 256 KB |
00_sample_02 | AC | 1 ms | 256 KB |
00_sample_03 | AC | 1 ms | 256 KB |
00_sample_04 | AC | 1 ms | 256 KB |
01_random_00 | WA | 7 ms | 4476 KB |
01_random_01 | WA | 7 ms | 4604 KB |
01_random_02 | WA | 6 ms | 4348 KB |
01_random_03 | AC | 1 ms | 256 KB |
01_random_04 | WA | 2 ms | 1148 KB |
01_random_05 | WA | 3 ms | 1532 KB |
01_random_06 | WA | 8 ms | 4604 KB |
01_random_07 | WA | 3 ms | 2940 KB |
01_random_08 | WA | 7 ms | 4476 KB |
01_random_09 | WA | 7 ms | 4476 KB |
02_X_positive_00 | WA | 6 ms | 4092 KB |
02_X_positive_01 | WA | 5 ms | 3196 KB |
02_X_positive_02 | WA | 6 ms | 4092 KB |
02_X_positive_03 | WA | 5 ms | 4476 KB |
02_X_positive_04 | WA | 8 ms | 4604 KB |
03_X_negative_00 | WA | 3 ms | 1916 KB |
03_X_negative_01 | WA | 8 ms | 4604 KB |
03_X_negative_02 | WA | 9 ms | 4604 KB |
03_X_negative_03 | WA | 5 ms | 3324 KB |
03_X_negative_04 | WA | 8 ms | 4604 KB |
04_T_large_00 | WA | 9 ms | 4604 KB |
04_T_large_01 | WA | 8 ms | 4604 KB |
04_T_large_02 | WA | 6 ms | 4092 KB |
04_T_large_03 | WA | 7 ms | 4476 KB |
04_T_large_04 | WA | 8 ms | 4476 KB |
04_T_small_00 | WA | 4 ms | 3580 KB |
04_T_small_01 | WA | 7 ms | 4476 KB |
04_T_small_02 | WA | 1 ms | 508 KB |
04_T_small_03 | AC | 3 ms | 2940 KB |
04_T_small_04 | WA | 4 ms | 2940 KB |
05_X_negative_large_00 | WA | 6 ms | 4348 KB |
05_X_negative_large_01 | AC | 6 ms | 4092 KB |
05_X_negative_large_02 | WA | 6 ms | 4476 KB |
05_X_negative_large_03 | WA | 8 ms | 4604 KB |
05_X_negative_large_04 | WA | 2 ms | 636 KB |
05_X_positive_large_00 | WA | 7 ms | 4604 KB |
05_X_positive_large_01 | WA | 8 ms | 4604 KB |
05_X_positive_large_02 | WA | 9 ms | 4604 KB |
05_X_positive_large_03 | WA | 1 ms | 508 KB |
05_X_positive_large_04 | WA | 4 ms | 3196 KB |
05_absX_large_00 | WA | 5 ms | 3836 KB |
05_absX_large_01 | WA | 8 ms | 4604 KB |
05_absX_large_02 | WA | 7 ms | 4604 KB |
05_absX_large_03 | WA | 3 ms | 3452 KB |
05_absX_large_04 | WA | 6 ms | 4092 KB |
05_absX_small_00 | WA | 3 ms | 2428 KB |
05_absX_small_01 | WA | 5 ms | 3580 KB |
05_absX_small_02 | WA | 9 ms | 4604 KB |
05_absX_small_03 | AC | 4 ms | 3452 KB |
05_absX_small_04 | WA | 6 ms | 3580 KB |
08_V_minimum_nonzero_00 | AC | 1 ms | 256 KB |
09_max_00 | WA | 9 ms | 4604 KB |
09_max_01 | WA | 9 ms | 4604 KB |
09_max_02 | WA | 9 ms | 4604 KB |
09_max_03 | WA | 9 ms | 4604 KB |
09_max_04 | WA | 9 ms | 4604 KB |
09_max_05 | AC | 11 ms | 4604 KB |
09_max_06 | AC | 9 ms | 4604 KB |
09_max_07 | AC | 9 ms | 4604 KB |
09_max_08 | AC | 9 ms | 4604 KB |
09_max_09 | AC | 9 ms | 4604 KB |
09_max_10 | WA | 9 ms | 4604 KB |
09_max_11 | WA | 9 ms | 4604 KB |
09_max_12 | WA | 9 ms | 4604 KB |
11_random_00 | WA | 87 ms | 4476 KB |
11_random_01 | WA | 313 ms | 10812 KB |
11_random_02 | WA | 170 ms | 11676 KB |
11_random_03 | WA | 167 ms | 12376 KB |
11_random_04 | WA | 352 ms | 19196 KB |
11_random_05 | WA | 190 ms | 11148 KB |
11_random_06 | WA | 102 ms | 5372 KB |
11_random_07 | WA | 304 ms | 11892 KB |
11_random_08 | WA | 169 ms | 12500 KB |
11_random_09 | WA | 292 ms | 20220 KB |
12_X_positive_00 | WA | 175 ms | 12540 KB |
12_X_positive_01 | WA | 236 ms | 12564 KB |
12_X_positive_02 | WA | 255 ms | 11548 KB |
12_X_positive_03 | WA | 102 ms | 4732 KB |
12_X_positive_04 | WA | 314 ms | 19580 KB |
13_X_negative_00 | WA | 157 ms | 11260 KB |
13_X_negative_01 | WA | 106 ms | 4604 KB |
13_X_negative_02 | WA | 200 ms | 11388 KB |
13_X_negative_03 | WA | 77 ms | 4988 KB |
13_X_negative_04 | WA | 222 ms | 12156 KB |
14_T_large_00 | WA | 269 ms | 11532 KB |
14_T_large_01 | WA | 249 ms | 12480 KB |
14_T_large_02 | WA | 188 ms | 11388 KB |
14_T_large_03 | WA | 329 ms | 11260 KB |
14_T_large_04 | WA | 227 ms | 11388 KB |
14_T_small_00 | WA | 50 ms | 5372 KB |
14_T_small_01 | WA | 252 ms | 12348 KB |
14_T_small_02 | WA | 297 ms | 11124 KB |
14_T_small_03 | WA | 261 ms | 11708 KB |
14_T_small_04 | WA | 294 ms | 12404 KB |
15_X_negative_large_00 | WA | 75 ms | 5116 KB |
15_X_negative_large_01 | WA | 267 ms | 10492 KB |
15_X_negative_large_02 | WA | 94 ms | 5116 KB |
15_X_negative_large_03 | WA | 99 ms | 4860 KB |
15_X_negative_large_04 | WA | 312 ms | 12220 KB |
15_X_positive_large_00 | WA | 106 ms | 4604 KB |
15_X_positive_large_01 | WA | 330 ms | 19964 KB |
15_X_positive_large_02 | WA | 47 ms | 5372 KB |
15_X_positive_large_03 | WA | 234 ms | 10460 KB |
15_X_positive_large_04 | WA | 262 ms | 11788 KB |
15_absX_large_00 | WA | 32 ms | 5244 KB |
15_absX_large_01 | WA | 232 ms | 11396 KB |
15_absX_large_02 | WA | 317 ms | 19836 KB |
15_absX_large_03 | WA | 164 ms | 10840 KB |
15_absX_large_04 | WA | 52 ms | 5372 KB |
15_absX_small_00 | WA | 29 ms | 5244 KB |
15_absX_small_01 | WA | 61 ms | 4988 KB |
15_absX_small_02 | WA | 305 ms | 18684 KB |
15_absX_small_03 | WA | 172 ms | 12508 KB |
15_absX_small_04 | WA | 21 ms | 5116 KB |
19_max_00 | WA | 329 ms | 19580 KB |
19_max_01 | WA | 304 ms | 20988 KB |
19_max_02 | WA | 354 ms | 19836 KB |
19_max_03 | WA | 341 ms | 20092 KB |
19_max_04 | WA | 349 ms | 20092 KB |
19_max_05 | AC | 434 ms | 20476 KB |
19_max_06 | AC | 333 ms | 20476 KB |
19_max_07 | AC | 296 ms | 19196 KB |
19_max_08 | AC | 338 ms | 20476 KB |
19_max_09 | AC | 327 ms | 19324 KB |
19_max_10 | WA | 341 ms | 19196 KB |
19_max_11 | WA | 293 ms | 20860 KB |
19_max_12 | WA | 343 ms | 19708 KB |