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
AC × 5
AC × 15
WA × 54
AC × 20
WA × 112
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