Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #15454058

Source Code Expand

Copy
```import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

@njit((i8[:], ), cache=True)
def main(XYP):
X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
N = len(X)
dp_X = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト
dp_X[0] = np.abs(X) * P
for n in range(N):
B = 1 << n
dp_X[B:2 * B] = np.minimum(dp_X[:B], np.abs(X - X[n]) * P)

dp_Y = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト
dp_Y[0] = np.abs(Y) * P
for n in range(N):
B = 1 << n
dp_Y[B:2 * B] = np.minimum(dp_Y[:B], np.abs(Y - Y[n]) * P)

popcount = np.zeros(1 << N, np.int64)
for n in range(N):
popcount[1 << n:1 << n + 1] = popcount[:1 << n] + 1

INF = 10**18
ans = np.full(N + 1, INF, np.int64)
for s in range(1 << N):
size = popcount[s]
t = s
while True:
u = s ^ t
cost = (np.minimum(dp_X[t], dp_Y[u])).sum()
ans[size] = min(ans[size], cost)
if t == 0:
break
t = (t - 1) & s
return ans

XYP = np.array(read().split(), np.int64)

ans = main(XYP)
print('\n'.join(map(str, ans.tolist())))```

#### Submission Info

Submission Time 2020-07-25 23:10:07+0900 E - M's Solution maspy Python (3.8.2) 500 1366 Byte AC 2256 ms 117544 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 500 / 500 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-corner-01.txt, 01-corner-02.txt, 01-corner-03.txt, 01-corner-04.txt, 01-corner-05.txt, 02-random-01.txt, 02-random-02.txt, 02-random-03.txt, 02-random-04.txt, 03-random-quarter-01.txt, 03-random-quarter-02.txt, 03-random-quarter-03.txt, 03-random-quarter-04.txt
Case Name Status Exec Time Memory
00-sample-01.txt 531 ms 107284 KB
00-sample-02.txt 516 ms 107948 KB
00-sample-03.txt 514 ms 107280 KB
01-corner-01.txt 1985 ms 116848 KB
01-corner-02.txt 2011 ms 116880 KB
01-corner-03.txt 2256 ms 116884 KB
01-corner-04.txt 561 ms 107276 KB
01-corner-05.txt 551 ms 107976 KB
02-random-01.txt 1025 ms 112440 KB
02-random-02.txt 2083 ms 117544 KB
02-random-03.txt 2028 ms 117544 KB
02-random-04.txt 2021 ms 116860 KB
03-random-quarter-01.txt 1055 ms 111624 KB
03-random-quarter-02.txt 2034 ms 117156 KB
03-random-quarter-03.txt 2027 ms 116884 KB
03-random-quarter-04.txt 2053 ms 116888 KB