Submission #44764533

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N; cin >> N;
  int X[N], Y[N];
  for (int n = 0; n < N; ++n) cin >> X[n] >> Y[n];
  auto distance = [&](int a, int b) {
    double x = X[a] - X[b];
    double y = Y[a] - Y[b];
    return sqrt(x*x + y*y);
  };

  double a[10000];
  double b[10000];

  unordered_map<int, unordered_map<int, double>> dp;
  dp[0][0] = 0;
  for (int n = 1; n < N - 1; ++n) {
    unordered_map<int, unordered_map<int, double>> next;
    for (auto &[skip, m] : dp) for (auto &[last, dist] : m) {
      if (skip > 60) continue;
      next[skip][n] = min(dist + distance(last, n), next[skip].contains(n) ? next[skip][n] : 1000000000.0);
      next[skip + 1][last] = min(dist, next[skip + 1].contains(last) ? next[skip + 1][last] : 1000000000.0);
    }
    dp = next;
  }
  unordered_map<int, double> p;
  for (auto &[skip, m] : dp) for (auto &[last, dist] : m) {
    p[skip] = min(dist + distance(last, N-1), p.contains(skip) ? p[skip] : 1000000000.0);
  }

  double ans = p[0];
  for (auto &[skip, v] : p) {
    if (skip == 0) continue;
    ans = min(ans, v + pow(2, skip - 1));
  }

  cout << std::setprecision(20) << ans << endl;
}

Submission Info

Submission Time
Task F - Shortcuts
User Steinberg
Language C++ 20 (gcc 12.2)
Score 500
Code Size 1216 Byte
Status AC
Exec Time 1929 ms
Memory 4356 KiB

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:14:10: warning: unused variable ‘a’ [-Wunused-variable]
   14 |   double a[10000];
      |          ^
Main.cpp:15:10: warning: unused variable ‘b’ [-Wunused-variable]
   15 |   double b[10000];
      |          ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 69
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All killer_01.txt, killer_02.txt, sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt, test_56.txt, test_57.txt, test_58.txt, test_59.txt, test_60.txt, test_61.txt, test_62.txt, test_63.txt, test_64.txt
Case Name Status Exec Time Memory
killer_01.txt AC 270 ms 4268 KiB
killer_02.txt AC 1197 ms 4300 KiB
sample_01.txt AC 1 ms 3944 KiB
sample_02.txt AC 1 ms 3992 KiB
sample_03.txt AC 1 ms 4040 KiB
test_01.txt AC 1 ms 3768 KiB
test_02.txt AC 2 ms 3852 KiB
test_03.txt AC 345 ms 4200 KiB
test_04.txt AC 60 ms 4236 KiB
test_05.txt AC 9 ms 4120 KiB
test_06.txt AC 1730 ms 4324 KiB
test_07.txt AC 1785 ms 4312 KiB
test_08.txt AC 1326 ms 4160 KiB
test_09.txt AC 977 ms 4296 KiB
test_10.txt AC 35 ms 4228 KiB
test_11.txt AC 1792 ms 4216 KiB
test_12.txt AC 1788 ms 4260 KiB
test_13.txt AC 1806 ms 4232 KiB
test_14.txt AC 1929 ms 4312 KiB
test_15.txt AC 1803 ms 4236 KiB
test_16.txt AC 1800 ms 4200 KiB
test_17.txt AC 1795 ms 4312 KiB
test_18.txt AC 1795 ms 4316 KiB
test_19.txt AC 78 ms 4128 KiB
test_20.txt AC 826 ms 4268 KiB
test_21.txt AC 706 ms 4260 KiB
test_22.txt AC 381 ms 4260 KiB
test_23.txt AC 642 ms 4296 KiB
test_24.txt AC 715 ms 4196 KiB
test_25.txt AC 1342 ms 4308 KiB
test_26.txt AC 491 ms 4164 KiB
test_27.txt AC 980 ms 4292 KiB
test_28.txt AC 1755 ms 4328 KiB
test_29.txt AC 1340 ms 4156 KiB
test_30.txt AC 1678 ms 4200 KiB
test_31.txt AC 873 ms 4228 KiB
test_32.txt AC 932 ms 4228 KiB
test_33.txt AC 113 ms 4252 KiB
test_34.txt AC 258 ms 4244 KiB
test_35.txt AC 1224 ms 4324 KiB
test_36.txt AC 1110 ms 4244 KiB
test_37.txt AC 781 ms 4164 KiB
test_38.txt AC 646 ms 4160 KiB
test_39.txt AC 1826 ms 4312 KiB
test_40.txt AC 1805 ms 4348 KiB
test_41.txt AC 1800 ms 4316 KiB
test_42.txt AC 1792 ms 4312 KiB
test_43.txt AC 1799 ms 4328 KiB
test_44.txt AC 1810 ms 4324 KiB
test_45.txt AC 1798 ms 4336 KiB
test_46.txt AC 1792 ms 4356 KiB
test_47.txt AC 1795 ms 4332 KiB
test_48.txt AC 1791 ms 4324 KiB
test_49.txt AC 1793 ms 4312 KiB
test_50.txt AC 1792 ms 4324 KiB
test_51.txt AC 1812 ms 4352 KiB
test_52.txt AC 1797 ms 4204 KiB
test_53.txt AC 1790 ms 4264 KiB
test_54.txt AC 1782 ms 4236 KiB
test_55.txt AC 1799 ms 4308 KiB
test_56.txt AC 1781 ms 4268 KiB
test_57.txt AC 1790 ms 4304 KiB
test_58.txt AC 1792 ms 4236 KiB
test_59.txt AC 1791 ms 4272 KiB
test_60.txt AC 1790 ms 4220 KiB
test_61.txt AC 1796 ms 4276 KiB
test_62.txt AC 1789 ms 4248 KiB
test_63.txt AC 1804 ms 4308 KiB
test_64.txt AC 1791 ms 4248 KiB