Submission #48412486

Source Code Expand

N,D=map(int,input().split())
A=list(map(int,input().split()))

w_list=[0]*(1<<N)
for s in range(1<<N):
  w=sum(A[i] for i in range(N) if (s>>i)&1)
  w_list[s]=w

dp=[w**2 for w in w_list]
for _ in range(2,D+1):
  new_dp=[3*10**18]*(1<<N)
  for s in range(1<<N):
    t=s
    while t:
      new_dp[s]=min(new_dp[s],dp[s^t]+w_list[t]**2)
      t=(t-1)&s
  dp=new_dp

print((dp[-1]*D-sum(A)**2)/D**2)

Submission Info

Submission Time
Task E - Lucky bag
User kyopro_friends
Language Python (PyPy 3.10-v7.3.12)
Score 525
Code Size 416 Byte
Status AC
Exec Time 574 ms
Memory 88424 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 525 / 525
Status
AC × 1
AC × 57
Set Name Test Cases
Sample example_00.txt
All example_00.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, random_00.txt, 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, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt, random_39.txt, random_40.txt, random_41.txt, random_42.txt, random_43.txt, random_44.txt, random_45.txt, random_46.txt, random_47.txt, random_48.txt, random_49.txt
Case Name Status Exec Time Memory
example_00.txt AC 54 ms 76604 KiB
hand_00.txt AC 573 ms 88424 KiB
hand_01.txt AC 541 ms 87680 KiB
hand_02.txt AC 339 ms 86244 KiB
hand_03.txt AC 55 ms 76588 KiB
hand_04.txt AC 54 ms 76732 KiB
hand_05.txt AC 574 ms 88072 KiB
random_00.txt AC 102 ms 84116 KiB
random_01.txt AC 130 ms 84348 KiB
random_02.txt AC 116 ms 84048 KiB
random_03.txt AC 172 ms 84932 KiB
random_04.txt AC 225 ms 84132 KiB
random_05.txt AC 542 ms 87932 KiB
random_06.txt AC 253 ms 83996 KiB
random_07.txt AC 558 ms 87868 KiB
random_08.txt AC 127 ms 84152 KiB
random_09.txt AC 312 ms 86136 KiB
random_10.txt AC 141 ms 83848 KiB
random_11.txt AC 279 ms 85548 KiB
random_12.txt AC 177 ms 84068 KiB
random_13.txt AC 416 ms 86876 KiB
random_14.txt AC 187 ms 84088 KiB
random_15.txt AC 355 ms 86100 KiB
random_16.txt AC 190 ms 83988 KiB
random_17.txt AC 496 ms 87364 KiB
random_18.txt AC 213 ms 83924 KiB
random_19.txt AC 456 ms 86880 KiB
random_20.txt AC 205 ms 85240 KiB
random_21.txt AC 205 ms 85596 KiB
random_22.txt AC 210 ms 85360 KiB
random_23.txt AC 245 ms 85348 KiB
random_24.txt AC 243 ms 85292 KiB
random_25.txt AC 244 ms 85604 KiB
random_26.txt AC 251 ms 85372 KiB
random_27.txt AC 242 ms 85368 KiB
random_28.txt AC 246 ms 85440 KiB
random_29.txt AC 275 ms 85752 KiB
random_30.txt AC 282 ms 86144 KiB
random_31.txt AC 288 ms 86212 KiB
random_32.txt AC 278 ms 85820 KiB
random_33.txt AC 288 ms 85628 KiB
random_34.txt AC 281 ms 85796 KiB
random_35.txt AC 313 ms 85872 KiB
random_36.txt AC 309 ms 86016 KiB
random_37.txt AC 316 ms 85804 KiB
random_38.txt AC 129 ms 84124 KiB
random_39.txt AC 127 ms 83976 KiB
random_40.txt AC 127 ms 83844 KiB
random_41.txt AC 141 ms 84156 KiB
random_42.txt AC 139 ms 84196 KiB
random_43.txt AC 162 ms 84180 KiB
random_44.txt AC 153 ms 84412 KiB
random_45.txt AC 279 ms 85568 KiB
random_46.txt AC 104 ms 83704 KiB
random_47.txt AC 92 ms 83852 KiB
random_48.txt AC 209 ms 85180 KiB
random_49.txt AC 130 ms 84088 KiB