Submission #2473254


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;
typedef long double ld;

ll X[1010];
ll dp[1010][1010][2];

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

int main() {
    const ll INF = 1L << 59;

    int N; cin >> N;
    REP(i, N) cin >> X[i];

    ld hi = 1000000000000000.0;
    ld lo = 1.0;

    REP(_, 100) {
        ld mid = (hi + lo) / 2;
        REP(i, N) REP(j, N) REP(k, 2) dp[i][j][k] = INF;
        REP(i, N) dp[i][i][0] = dp[i][i][1] = abs(X[i]);

        REP2 (len, 1, N+1) REP(l, N) REP(i, 2) REP(j, 2) {
            int r = l + len - 1;
            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) {
                ll 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) {
                ll 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) {
                ll 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) {
                ll 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 (min(dp[0][N-1][0], dp[0][N-1][1]) != INF) hi = mid;
        else lo = mid;
    }

    cout.precision(20);
    cout << fixed  << hi << endl;
}

Submission Info

Submission Time
Task B - 道迷い
User nebukuro09
Language C++14 (GCC 5.4.1)
Score 120
Code Size 1790 Byte
Status AC
Exec Time 1989 ms
Memory 16000 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 70 / 70 50 / 50
Status
AC × 3
AC × 49
AC × 83
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_15.txt, subtask1_16.txt, subtask1_19.txt, subtask1_20.txt, subtask1_22.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt, subtask1_43.txt, subtask1_44.txt, subtask1_45.txt, subtask1_46.txt, subtask1_47.txt, subtask1_48.txt, subtask1_49.txt, subtask1_50.txt, subtask1_51.txt, subtask1_52.txt, subtask1_53.txt, subtask1_54.txt, subtask1_55.txt, subtask1_56.txt, subtask1_57.txt, subtask1_58.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_15.txt, subtask1_16.txt, subtask1_19.txt, subtask1_20.txt, subtask1_22.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt, subtask1_43.txt, subtask1_44.txt, subtask1_45.txt, subtask1_46.txt, subtask1_47.txt, subtask1_48.txt, subtask1_49.txt, subtask1_50.txt, subtask1_51.txt, subtask1_52.txt, subtask1_53.txt, subtask1_54.txt, subtask1_55.txt, subtask1_56.txt, subtask1_57.txt, subtask1_58.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_15.txt, subtask2_16.txt, subtask2_19.txt, subtask2_20.txt, subtask2_22.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt, subtask2_41.txt, subtask2_42.txt, subtask2_43.txt, subtask2_44.txt, subtask2_45.txt, subtask2_46.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask1_07.txt AC 74 ms 3200 KB
subtask1_08.txt AC 74 ms 3200 KB
subtask1_09.txt AC 74 ms 3200 KB
subtask1_10.txt AC 74 ms 3200 KB
subtask1_11.txt AC 74 ms 3200 KB
subtask1_12.txt AC 74 ms 3200 KB
subtask1_15.txt AC 74 ms 3200 KB
subtask1_16.txt AC 74 ms 3200 KB
subtask1_19.txt AC 74 ms 3200 KB
subtask1_20.txt AC 74 ms 3200 KB
subtask1_22.txt AC 72 ms 3200 KB
subtask1_24.txt AC 72 ms 3200 KB
subtask1_25.txt AC 74 ms 3200 KB
subtask1_26.txt AC 73 ms 3200 KB
subtask1_27.txt AC 74 ms 3200 KB
subtask1_28.txt AC 74 ms 3200 KB
subtask1_29.txt AC 74 ms 3200 KB
subtask1_30.txt AC 74 ms 3200 KB
subtask1_31.txt AC 74 ms 3200 KB
subtask1_32.txt AC 74 ms 3200 KB
subtask1_33.txt AC 73 ms 3200 KB
subtask1_34.txt AC 73 ms 3200 KB
subtask1_35.txt AC 73 ms 3200 KB
subtask1_36.txt AC 73 ms 3200 KB
subtask1_37.txt AC 73 ms 3200 KB
subtask1_38.txt AC 73 ms 3200 KB
subtask1_39.txt AC 73 ms 3200 KB
subtask1_40.txt AC 72 ms 3200 KB
subtask1_41.txt AC 73 ms 3200 KB
subtask1_42.txt AC 73 ms 3200 KB
subtask1_43.txt AC 73 ms 3200 KB
subtask1_44.txt AC 73 ms 3200 KB
subtask1_45.txt AC 73 ms 3200 KB
subtask1_46.txt AC 74 ms 3200 KB
subtask1_47.txt AC 1 ms 256 KB
subtask1_48.txt AC 1 ms 256 KB
subtask1_49.txt AC 1 ms 256 KB
subtask1_50.txt AC 1 ms 256 KB
subtask1_51.txt AC 1 ms 256 KB
subtask1_52.txt AC 1 ms 256 KB
subtask1_53.txt AC 1 ms 256 KB
subtask1_54.txt AC 1 ms 256 KB
subtask1_55.txt AC 1 ms 256 KB
subtask1_56.txt AC 1 ms 256 KB
subtask1_57.txt AC 1 ms 256 KB
subtask1_58.txt AC 1 ms 256 KB
subtask2_07.txt AC 1840 ms 16000 KB
subtask2_08.txt AC 1838 ms 16000 KB
subtask2_09.txt AC 1954 ms 16000 KB
subtask2_10.txt AC 1936 ms 16000 KB
subtask2_11.txt AC 1876 ms 16000 KB
subtask2_12.txt AC 1848 ms 16000 KB
subtask2_15.txt AC 1885 ms 16000 KB
subtask2_16.txt AC 1860 ms 16000 KB
subtask2_19.txt AC 1842 ms 16000 KB
subtask2_20.txt AC 1846 ms 16000 KB
subtask2_22.txt AC 1820 ms 16000 KB
subtask2_24.txt AC 1861 ms 16000 KB
subtask2_25.txt AC 1850 ms 16000 KB
subtask2_26.txt AC 1917 ms 16000 KB
subtask2_27.txt AC 1876 ms 16000 KB
subtask2_28.txt AC 1981 ms 16000 KB
subtask2_29.txt AC 1943 ms 16000 KB
subtask2_30.txt AC 1872 ms 16000 KB
subtask2_31.txt AC 1976 ms 16000 KB
subtask2_32.txt AC 1886 ms 16000 KB
subtask2_33.txt AC 1869 ms 16000 KB
subtask2_34.txt AC 1849 ms 16000 KB
subtask2_35.txt AC 1926 ms 16000 KB
subtask2_36.txt AC 1864 ms 16000 KB
subtask2_37.txt AC 1871 ms 16000 KB
subtask2_38.txt AC 1838 ms 16000 KB
subtask2_39.txt AC 1837 ms 16000 KB
subtask2_40.txt AC 1879 ms 16000 KB
subtask2_41.txt AC 1861 ms 16000 KB
subtask2_42.txt AC 1836 ms 16000 KB
subtask2_43.txt AC 1895 ms 16000 KB
subtask2_44.txt AC 1823 ms 16000 KB
subtask2_45.txt AC 1843 ms 16000 KB
subtask2_46.txt AC 1989 ms 16000 KB