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 |
|
|
|
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 |