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

Submission #15463739

Source Code Expand

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

@njit((i8[:], i8[:]), cache=True)
def f(X, P):
INF = 10**18
ind = np.argsort(X)
X, P = X[ind], P[ind]
N = len(X)
if N == 0:
return np.array([0], np.int64)
# [0, i) から X[j] までのコストの和
dp1 = np.zeros((N + 1, N), np.int64)
for i in range(N):
for j in range(N):
dp1[i + 1, j] = np.abs(X[i] - X[j]) * P[i]
for i in range(N):
dp1[i + 1] += dp1[i]

# [l, r]をひとまとめにするときのコストの最小値
dp2 = np.empty((N, N), np.int64)
for l in range(N):
for r in range(l, N):
dp2[l, r] = (dp1[r + 1] - dp1[l]).min()

# [0,i] を j 件でとる場合のコストの最小値
dp3 = np.full((N, N + 1), INF, np.int64)
for i in range(N):
dp3[i, 0] = np.sum(X[:i + 1] * P[:i + 1])
dp3[i, 1] = dp2[0, i]
for j in range(i):
# [0,j] + (j,i]
dp3[i, 1:] = np.minimum(dp3[i, 1:], dp3[j, :-1] + dp2[j + 1, i])
return dp3[-1]

@njit((i8[:], i8[:]), cache=True)
def merge(A, B):
LA, LB = len(A), len(B)
INF = 10**18
C = np.full(LA + LB - 1, INF, np.int64)
for i in range(LA):
C[i:i + LB] = np.minimum(C[i:i + LB], A[i] + B)
return C

@njit((i8[:], ), cache=True)
def main(XYP):
X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
N = len(X)
INF = 10**18
ans = np.full(N + 1, INF, np.int64)
full = (1 << N) - 1
for x in range(1 << N):
i_x = np.bool_([x & (1 << i) for i in range(N)])
i_y = ~i_x
dp = f(X[i_x & (X >= 0)], P[i_x & (X >= 0)])
dp = merge(dp, f(-X[i_x & (X < 0)], P[i_x & (X < 0)]))
dp = merge(dp, f(Y[i_y & (Y >= 0)], P[i_y & (Y >= 0)]))
dp = merge(dp, f(-Y[i_y & (Y < 0)], P[i_y & (Y < 0)]))
ans = np.minimum(ans, dp)
return ans

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

#### Submission Info

Submission Time 2020-07-26 12:58:28+0900 E - M's Solution maspy Python (3.8.2) 500 2202 Byte AC 1308 ms 111880 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 496 ms 111220 KB
00-sample-02.txt 495 ms 111876 KB
00-sample-03.txt 491 ms 110640 KB
01-corner-01.txt 1130 ms 111180 KB
01-corner-02.txt 1308 ms 111532 KB
01-corner-03.txt 1075 ms 111160 KB
01-corner-04.txt 503 ms 111124 KB
01-corner-05.txt 492 ms 111240 KB
02-random-01.txt 782 ms 111880 KB
02-random-02.txt 1071 ms 111140 KB
02-random-03.txt 1082 ms 111368 KB
02-random-04.txt 1082 ms 111500 KB
03-random-quarter-01.txt 859 ms 111868 KB
03-random-quarter-02.txt 1254 ms 111424 KB
03-random-quarter-03.txt 1288 ms 111168 KB
03-random-quarter-04.txt 1274 ms 111188 KB