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

Submission #15448470

Source Code Expand

Copy
```import sys
import numpy as np

def main(XYP):
X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
N = len(X)
dp = np.empty((3**N, N), np.int64)  # 建設、人 -> コスト
dp[0] = np.minimum(np.abs(X), np.abs(Y)) * P
size = np.empty(3**N, np.int64)
size[0] = 0
for n in range(N):
B = 3**n
DX = np.abs(X - X[n]) * P
DY = np.abs(Y - Y[n]) * P
dp[B:2 * B] = np.minimum(dp[:B], DX)
dp[2 * B:3 * B] = np.minimum(dp[:B], DY)
size[B:2 * B] = size[:B] + 1
size[2 * B:3 * B] = size[:B] + 1
ans = np.full(N + 1, 10**18, np.int64)
for s in range(3**N):
n = size[s]
ans[n] = min(ans[n], dp[s].sum())
return ans

if sys.argv[-1] == 'ONLINE_JUDGE':
import numba
from numba.pycc import CC
i8 = numba.int64
cc = CC('my_module')

def cc_export(f, signature):
cc.export(f.__name__, signature)(f)
return numba.njit(f)

main = cc_export(main, (i8[:], ))
cc.compile()

from my_module import main

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

#### Submission Info

Submission Time 2020-07-25 22:28:49+0900 E - M's Solution maspy Python (3.8.2) 0 1295 Byte MLE 2849 ms 2326984 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 0 / 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 115 ms 27096 KB
00-sample-02.txt 111 ms 27080 KB
00-sample-03.txt 115 ms 27324 KB
01-corner-01.txt 2849 ms 2326672 KB
01-corner-02.txt 2786 ms 2326640 KB
01-corner-03.txt 2825 ms 2326664 KB
01-corner-04.txt 112 ms 26844 KB
01-corner-05.txt 112 ms 27008 KB
02-random-01.txt 969 ms 756096 KB
02-random-02.txt 2791 ms 2326772 KB
02-random-03.txt 2814 ms 2326708 KB
02-random-04.txt 2807 ms 2326760 KB
03-random-quarter-01.txt 955 ms 755928 KB
03-random-quarter-02.txt 2809 ms 2326984 KB
03-random-quarter-03.txt 2786 ms 2326636 KB
03-random-quarter-04.txt 2846 ms 2326660 KB