提出 #35636696

ソースコード 拡げる

popcount=[0]*32
for i in range(1,32):
  popcount[i]=popcount[i//2]+(i%2)

def hypot(p,q):
  return ((p[0]-q[0])**2+(p[1]-q[1])**2)**0.5

N,M=map(int,input().split())
pos=[tuple(map(int,input().split())) for _ in range(N+M)]

dp=[[1e18]*(1<<(N+M)) for _ in range(N+M)]
for i in range(N+M): dp[i][1<<i]=hypot(pos[i],(0,0))

for s in range(1,1<<(N+M)):
  coef=0.5**popcount[s>>N]
  for i in range(N+M):
    if not (s>>i)&1: continue
    for j in range(N+M):
      if (s>>j)&1: continue
      new_dist=dp[i][s]+hypot(pos[i],pos[j])*coef
      if dp[j][s^(1<<j)]>new_dist: dp[j][s^(1<<j)]=new_dist

ans=1e18
for i in range(N+M):
  for s in range((1<<N)-1,1<<(N+M),1<<N):
    ans=min(ans,dp[i][s]+hypot(pos[i],(0,0))*0.5**popcount[s>>N])

print(f"{ans:.10f}")

提出情報

提出日時
問題 E - Booster
ユーザ kyopro_friends
言語 PyPy3 (7.3.0)
得点 500
コード長 782 Byte
結果 AC
実行時間 1106 ms
メモリ 92596 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 3
AC × 23
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
random_01.txt AC 1106 ms 92552 KiB
random_02.txt AC 119 ms 75352 KiB
random_03.txt AC 1087 ms 92272 KiB
random_04.txt AC 78 ms 71024 KiB
random_05.txt AC 1050 ms 92568 KiB
random_06.txt AC 101 ms 74948 KiB
random_07.txt AC 89 ms 74604 KiB
random_08.txt AC 513 ms 83072 KiB
random_09.txt AC 1070 ms 92596 KiB
random_10.txt AC 186 ms 76500 KiB
random_11.txt AC 128 ms 75888 KiB
random_12.txt AC 99 ms 75152 KiB
random_13.txt AC 1077 ms 92236 KiB
random_14.txt AC 1055 ms 92380 KiB
random_15.txt AC 291 ms 78716 KiB
random_16.txt AC 97 ms 74960 KiB
random_17.txt AC 1048 ms 92484 KiB
random_18.txt AC 69 ms 64668 KiB
random_19.txt AC 86 ms 74660 KiB
random_20.txt AC 48 ms 62380 KiB
sample_01.txt AC 51 ms 62364 KiB
sample_02.txt AC 49 ms 62488 KiB
sample_03.txt AC 50 ms 62308 KiB