Submission #2473222

---

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, std.regex;

void main() {
    immutable long INF = 1L << 59;

    auto N = readln.chomp.to!int;
    auto X = N.iota.map!(_ => readln.chomp.to!long).array;

    bool in_time(int i, long dist, real vel) {
        return dist / vel <= abs(X[i]);
    }

    real hi = 10L^^15;
    real lo = 1;

    foreach (_; 0..100) {
        real mid = (hi + lo) / 2;
        auto dp = new long[][][](N, N, 2);
        foreach (i; 0..N) foreach (j; 0..N) dp[i][j].fill(INF);
        foreach (i; 0..N) dp[i][i][0] = dp[i][i][1] = abs(X[i]);

        foreach (len; 1..N+1) {
            foreach (l; 0..N) {
                int r = l + len - 1;
                foreach (i; 0..2) {
                    foreach (j; 0..2) {
                        int nl = l;
                        int nr = r;
                        if (j == 0) nl -= 1;
                        else        nr += 1;
                        if (nl < 0 || nr >= N) continue;

                        if (i == 0 && j == 0) {
                            long nd = dp[l][r][i] + X[l] - X[nl];
                            if (in_time(nl, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd);
                        } else if (i == 0 && j == 1) {
                            long nd = dp[l][r][i] + X[nr] - X[l];
                            if (in_time(nr, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd);
                        } else if (i == 1 && j == 0) {
                            long nd = dp[l][r][i] + X[r] - X[nl];
                            if (in_time(nl, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd);
                        } else if (i == 1 && j == 1) {
                            long nd = dp[l][r][i] + X[nr] - X[r];
                            if (in_time(nr, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd);
                        }
                    }
                }
            }
        }

        if (dp[0][N-1].reduce!min != INF) hi = mid;
        else lo = mid;
    }

    writefln("%.9f", hi);
}

Submission Info

Judge Result