Problem:
 Score: 500 points    Problem Statement  New AtCoder City has an infinite grid of streets, as follows:   At the center of the city stands a clock tower. Let (0, 0) be the coordinates of this point.  A straight street, which we will call East-West Main Street , runs east-west and passes the clock tower. It corresponds to the x -axis in the two-dimensional coordinate plane.  There are also other infinitely many streets parallel to East-West Main Street, with a distance of 1 between them. They correspond to the lines \ldots, y = -2, y = -1, y = 1, y = 2, \ldots in the two-dimensional coordinate plane.  A straight street, which we will call North-South Main Street , runs north-south and passes the clock tower. It corresponds to the y -axis in the two-dimensional coordinate plane.  There are also other infinitely many streets parallel to North-South Main Street, with a distance of 1 between them. They correspond to the lines \ldots, x = -2, x = -1, x = 1, x = 2, \ldots in the two-dimensional coordinate plane.   There are N residential areas in New AtCoder City. The i -th area is located at the intersection with the coordinates (X_i, Y_i) and has a population of P_i . Each citizen in the city lives in one of these areas.  The city currently has only two railroads, stretching infinitely, one along East-West Main Street and the other along North-South Main Street. M-kun, the mayor, thinks that they are not enough for the commuters, so he decides to choose K streets and build a railroad stretching infinitely along each of those streets.  Let the walking distance of each citizen be the distance from his/her residential area to the nearest railroad. M-kun wants to build railroads so that the sum of the walking distances of all citizens, S , is minimized.  For each K = 0, 1, 2, \dots, N , what is the minimum possible value of S after building railroads?      Constraints   1 \leq N \leq 15  -10 \ 000 \leq X_i \leq 10 \ 000  -10 \ 000 \leq Y_i \leq 10 \ 000  1 \leq P_i \leq 1 \ 000 \ 000  The locations of the N residential areas, (X_i, Y_i) , are all distinct.  All values in input are integers.         Input  Input is given from Standard Input in the following format:  N  X_1  Y_1  P_1  X_2  Y_2  P_2  :  :  :  X_N  Y_N  P_N       Output  Print the answer in N+1 lines. The i -th line (i = 1, \ldots, N+1) should contain the minimum possible value of S after building railroads for the case K = i-1 .        Sample Input 1 3
1 2 300
3 3 600
1 4 800      Sample Output 1 2900
900
0
0  When K = 0 , the residents of Area 1 , 2 , and 3 have to walk the distances of 1 , 3 , and 1 , respectively, to reach a railroad. Thus, the sum of the walking distances of all citizens, S , is 1 \times 300 + 3 \times 600 + 1 \times 800 = 2900 .  When K = 1 , if we build a railroad along the street corresponding to the line y = 4 in the coordinate plane, the walking distances of the citizens of Area 1 , 2 , and 3 become 1 , 1 , and 0 , respectively. Then, S = 1 \times 300 + 1 \times 600 + 0 \times 800 = 900 . We have many other options for where we build the railroad, but none of them makes S less than 900 .  When K = 2 , if we build a railroad along the street corresponding to the lines x = 1 and x = 3 in the coordinate plane, all citizens can reach a railroad with the walking distance of 0 , so S = 0 . We can also have S = 0 when K = 3 .  The figure below shows the optimal way to build railroads for the cases K = 0, 1, 2 . The street painted blue represents the roads along which we build railroads.        Sample Input 2 5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400      Sample Output 2 13800
1600
0
0
0
0  The figure below shows the optimal way to build railroads for the cases K = 1, 2 .        Sample Input 3 6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200      Sample Output 3 26700
13900
3200
1200
0
0
0  The figure below shows the optimal way to build railroads for the case K = 3 .        Sample Input 4 8
2 2 286017
3 1 262355
2 -2 213815
1 -3 224435
-2 -2 136860
-3 -1 239338
-2 2 217647
-1 3 141903      Sample Output 4 2576709
1569381
868031
605676
366338
141903
0
0
0  The figure below shows the optimal way to build railroads for the case K = 4 .

Solution (Python):
def main():
    n = int(input())
    xyp = [list(map(int, input().split())) for _ in [0]*n]
    d = []

    def calc(seq):
        m = len(seq)
        dp = [[10**15]*(m+1) for _ in [0]*(m+1)]
        dp[0][0] = 0
        for i in range(m):
            s = seq[i][0]
            for j in range(i+1):
                temp = dp[j][0]
                for a, b in seq[:i+1]:
                    temp += min(abs(a), s-a)*b
                dp[j+1][i+1] = min(dp[j+1][i+1], temp)
                temp2 = 10**15
                for k in range(1, i+1):
                    temp = dp[j][k]
                    t = seq[k-1][0]
                    for a, b in seq[k:i+1]:
                        temp += min(abs(a), a-t, s-a)*b
                    temp2 = min(temp2, temp)
                dp[j+1][i+1] = min(dp[j+1][i+1], temp2)
        for i in range(m+1):
            for a, b in seq[:m]:
                dp[i][0] += abs(a)*b
            for k in range(1, m+1):
                t = seq[k-1][0]
                temp = 0
                for a, b in seq[k:m]:
                    temp += min(abs(a), a-t)*b
                dp[i][k] += temp
        for i in range(m+1):
            dp[i] = min(dp[i])
        dp += [0]*(n-m)
        return dp

    xyp.sort()
    for i in range(2**n):
        x_list, y_list = [], []
        for j in range(n):
            x, y, p = xyp[j]
            if i & 1:
                x_list.append([x, p])
            else:
                y_list.append([y, p])
            i >>= 1
        y_list.sort()
        d.append([calc(x_list), calc(y_list)])

    ans = [10**15]*(n+1)
    for x, y in d:
        for i in range(n+1):
            for j in range(n-i+1):
                ans[i+j] = min(ans[i+j], x[i]+y[j])
    for i in ans:
        print(i)


main()

Solution (Python):
def main():
    n = int(input())
    xyp = [list(map(int, input().split())) for _ in [0]*n]
    d = []

    def calc(seq):
        m = len(seq)
        dp = [[10**15]*(m+1) for _ in [0]*(m+1)]
        dp[0][0] = 0
        for i in range(m):
            for j in range(i+1):
                temp = dp[j][0]
                for a, b in seq[:i+1]:
                    temp += min(abs(a), seq[i][0]-a)*b
                dp[j+1][i+1] = min(dp[j+1][i+1], temp)
                for k in range(1, i+1):
                    temp = dp[j][k]
                    for a, b in seq[k:i+1]:
                        temp += min(abs(a), a-seq[k-1][0], seq[i][0]-a)*b
                    dp[j+1][i+1] = min(dp[j+1][i+1], temp)
        for i in range(m+1):
            for a, b in seq[:m]:
                dp[i][0] += abs(a)*b
            for k in range(1, m+1):
                for a, b in seq[k:m]:
                    dp[i][k] += min(abs(a), a-seq[k-1][0])*b
        for i in range(m+1):
            dp[i] = min(dp[i])
        dp += [0]*(n-m)
        return dp

    xyp.sort()
    for i in range(2**n):
        x_list, y_list = [], []
        for j in range(n):
            x, y, p = xyp[j]
            if i & 1:
                x_list.append([x, p])
            else:
                y_list.append([y, p])
            i >>= 1
        y_list.sort()
        d.append([calc(x_list), calc(y_list)])

    ans = [10**15]*(n+1)
    for x, y in d:
        for i in range(n+1):
            for j in range(n-i+1):
                ans[i+j] = min(ans[i+j], x[i]+y[j])
    for i in ans:
        print(i)


main()

Solution (Python):
N = int(input())
X = []; Y = []; P = []
INF = float("inf")
for i in range(N):
  x,y,p = list(map(int,input().split()))
  X.append(x);Y.append(y);P.append(p)
ans = [INF for _ in range(N+1)] 

def calc(A):
  n = len(A) 
  A.sort()
  dp = [[INF]*(n+1) for _ in range(n+1)] 
  dp[0][0] = 0
  for l in range(n):
    for r in range(l+1,n+1):
      now = INF
      for k in range(l,r):
        s = 0
        for i in range(l,r):
          s += abs(A[i][0]-A[k][0])*A[i][1]
        now = min(now,s)
      for j in range(n):
        dp[r][j+1] = min(dp[r][j+1], dp[l][j]+now)
      now = 0
      for i in range(l,r):
        now += abs(A[i][0])*A[i][1]
      for j in range(n+1):
        dp[r][j] = min(dp[r][j], dp[l][j]+now)

  
  res = [INF for _ in range(n+1)] 
  for j in range(n+1):
    res[j] = dp[n][j]

  return res
    

for s in range(1<<N): 
  AX = [];AY = [] 
  for i in range(N):
    if (s>>i)&1 == 1: 
      AX.append((X[i],P[i]))
    else:
      AY.append((Y[i],P[i]))
    
  dx = calc(AX)
  dy = calc(AY)
  for i in range(len(dx)):
    for j in range(len(dy)):
      ans[i+j] = min(ans[i+j],dx[i]+dy[j])
for t in ans:
  print(t)

Solution (Python):
import sys

N = int(input())
XYP = [list(map(int, input().split())) for _ in range(N)]

bits = 1 << N

xmemo = [sys.maxsize]*(N*bits)
ymemo = [sys.maxsize]*(N*bits)

for b in range(bits):
  for i in range(N):
    xmemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][0]), xmemo[b*N+i])
    ymemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][1]), ymemo[b*N+i])
    if not (b & (1<<i)):
      continue
    for j in range(N):
      xmemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][0]-XYP[j][0]), xmemo[b*N+j])
      ymemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][1]-XYP[j][1]), ymemo[b*N+j])
      
ans = [sys.maxsize]*(N+1)

for b in range(bits):
  b_ = b
  cnt = bin(b_).count('1')
  while b_ >= 0:
    b_ &= b
    yi = b - b_
    tmp = 0
    for i in range(N):
      tmp += min(xmemo[b_*N+i], ymemo[yi*N+i])
    ans[cnt] = min(ans[cnt], tmp)
    b_ -= 1
  
for i in range(N+1):
  print(ans[i])

Solution (Python):
def main():
    n = int(input())
    xyp = [list(map(int, input().split())) for _ in [0]*n]
    d = []

    def calc(seq):
        m = len(seq)
        dp = [[0] for _ in [0]*1]  
        for i in range(m):
            dp2 = [[10**15]*(i+2) for _ in [0]*(i+2)]
            for j in range(i+1):
                for k in range(i+1):
                    dp2[j][k] = min(dp2[j][k], dp[j][k])
                    temp = dp[j][k]
                    if k == 0:
                        for l in range(k, i+1):
                            temp += min(abs(seq[l][0]), seq[i]
                                        [0]-seq[l][0])*seq[l][1]
                    else:
                        for l in range(k, i+1):
                            temp += min(abs(seq[l][0]), seq[l]
                                        [0]-seq[k-1][0], seq[i][0]-seq[l][0])*seq[l][1]
                    dp2[j+1][i+1] = min(dp2[j+1][i+1], temp)
            dp = dp2
        for i in range(m+1):
            for l in range(m):
                dp[i][0] += abs(seq[l][0])*seq[l][1]
            for k in range(1, m+1):
                for l in range(k, m):
                    dp[i][k] += min(abs(seq[l][0]), seq[l]
                                    [0]-seq[k-1][0])*seq[l][1]
        for i in range(m+1):
            dp[i] = min(dp[i])
        dp += [0]*(n-m)
        return dp

    xyp.sort()
    for i in range(2**n):
        x_list, y_list = [], []
        for j in range(n):
            x, y, p = xyp[j]
            if i & 1:
                x_list.append([x, p])
            else:
                y_list.append([y, p])
            i >>= 1
        y_list.sort()
        d.append([calc(x_list), calc(y_list)])

    ans = [10**15]*(n+1)
    for x, y in d:
        for i in range(n+1):
            for j in range(n-i+1):
                ans[i+j] = min(ans[i+j], x[i]+y[j])
    for i in ans:
        print(i)


main()

Solution (Python):
import sys
input = sys.stdin.readline

INF = float('inf')

N = int(input().strip())
data = [list(map(int, input().split())) for _ in range(N)]
cost_b = []
cost_D = []
for b in range(1<<N):
  towns = []
  cost = INF
  for i in range(N):
    if (b>>i)&1:
      towns.append(data[i])
  for i in range(len(towns)):
    X = towns[i][0]
    cost = min(cost,sum(abs(towns[j][0]-X)*towns[j][2] for j in range(len(towns))))
  for i in range(len(towns)):
    Y = towns[i][1]
    cost = min(cost,sum(abs(towns[j][1]-Y)*towns[j][2] for j in range(len(towns))))
  if len(towns) == 0:
    cost = 0
  cost_b.append(cost)
  cost_D.append(sum(min(abs(towns[j][0]),abs(towns[j][1]))*towns[j][2] for j in range(len(towns))))

dp = [[INF]*(N+1) for i in range(1<<N)]

for i in range(1<<N):
  dp[i][0] = cost_D[i]
count = 0
for k in range(1,N+1):
  for i in range(1<<N)[::-1]:
    x = i
    while x>=0:
      x &= i
      new = dp[i-x][k-1]+cost_b[x]
      if dp[i][k] > new:
        dp[i][k] = new
      if new == 0:
        break
      x -= 1
for i in range(N+1):
  print(dp[-1][i])

Solution (Python):
import sys
input = sys.stdin.readline

INF = float('inf')

N = int(input().strip())
data = [list(map(int, input().split())) for _ in range(N)]
cost_b = []
cost_D = []
for b in range(1<<N):
  towns = []
  cost = INF
  for i in range(N):
    if (b>>i)&1:
      towns.append(data[i])
  for i in range(len(towns)):
    X = towns[i][0]
    cost = min(cost,sum(abs(towns[j][0]-X)*towns[j][2] for j in range(len(towns))))
  for i in range(len(towns)):
    Y = towns[i][1]
    cost = min(cost,sum(abs(towns[j][1]-Y)*towns[j][2] for j in range(len(towns))))
  if len(towns) == 0:
    cost = 0
  cost_b.append(cost)
  cost_D.append(sum(min(abs(towns[j][0]),abs(towns[j][1]))*towns[j][2] for j in range(len(towns))))

dp = [[INF]*(N+1) for i in range(1<<N)]

for i in range(1<<N):
  dp[i][0] = cost_D[i]
count = 0
for k in range(1,N+1):
  for i in range(1<<N)[::-1]:
    x = i
    while x>=0:
      x &= i
      new = dp[i-x][k-1]+cost_b[x]
      if dp[i][k] > new:
        dp[i][k] = new
      if new == 0:
        break
      x -= 1
for i in range(N+1):
  print(dp[-1][i])

Solution (Python):
import sys
input = sys.stdin.readline

INF = float('inf')

N = int(input().strip())
data = [list(map(int, input().split())) for _ in range(N)]
cost_b = []
cost_D = []
for b in range(1<<N):
  towns = []
  cost = INF
  for i in range(N):
    if (b>>i)&1:
      towns.append(data[i])
  for i in range(len(towns)):
    X = towns[i][0]
    cost = min(cost,sum(abs(towns[j][0]-X)*towns[j][2] for j in range(len(towns))))
  for i in range(len(towns)):
    Y = towns[i][1]
    cost = min(cost,sum(abs(towns[j][1]-Y)*towns[j][2] for j in range(len(towns))))
  if len(towns) == 0:
    cost = 0
  cost_b.append(cost)
  cost_D.append(sum(min(abs(towns[j][0]),abs(towns[j][1]))*towns[j][2] for j in range(len(towns))))

dp = [[INF]*(N+1) for i in range(1<<N)]

for i in range(1<<N):
  dp[i][0] = cost_D[i]
count = 0
for k in range(1,N+1):
  for i in reversed(range(1<<N)):
    x = i
    while x>=0:
      x &= i
      new = dp[i-x][k-1]+cost_b[x]
      if dp[i][k] > new:
        dp[i][k] = new
      if new == 0:
        break
      x -= 1
for i in range(N+1):
  print(dp[-1][i])

Solution (Python):
N = int(input())
X = []
Y = []
P = []
for _ in range(N):
    x,y,p = map(int,input().split())
    X.append(x)
    Y.append(y)
    P.append(p)
DX = [[0]*N for _ in range(1<<N)]
DY = [[0]*N for _ in range(1<<N)]

for i,x in enumerate(X):
    for k in range(1<<N):
        d = abs(x)
        for j,xx in enumerate(X):
            if k & (1<<j):
                d = min(d,abs(xx-x))
        DX[k][i] = d*P[i]
for i,y in enumerate(Y):
    for k in range(1<<N):
        d = abs(y)
        for j,yy in enumerate(Y):
            if k & (1<<j):
                d = min(d,abs(yy-y))
        DY[k][i] = d*P[i]

ANS = [1<<100]*(N+1)
PC = [0]*(1<<N)
for i in range(1,1<<N):
    PC[i] = PC[i^1] + 1 if i%2 else PC[i//2] 
RA = []
for i in range(1<<N):
    t = []
    for j in range(N):
        if i&(1<<j):
            t.append(j)
    RA.append(t)

mm = (1 << N) - 1
for i in range(1 << N):
    m = i ^ mm
    j = m
    dxi = DX[i]
    pci = PC[i]
    while 1:
        dyj = DY[j]
        ans = 0
        for k in RA[i^j^mm]:
            ans += min(dxi[k], dyj[k])
        
        pc = pci + PC[j]
        ANS[pc] = min(ANS[pc], ans)
        
        if not j:
            break
        j = m & (j - 1)
print(*ANS ,sep="\n")

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@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)
    
    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]

    
    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()

    
    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):
            
            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

N = int(readline())
XYP = np.array(read().split(), np.int64)

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

Solution (Python):


 
import sys
import numpy as np
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def resolve(XYP):
	X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
	N = len(X)
	X_cost = np.empty((1 << N,N), np.int64)
	X_cost[0] = np.abs(X) * P
	for n in range(N):
		B = 1 << n
		X_cost[B:2 * B] = np.minimum(X_cost[:B], np.abs((X-X[n]) * P))
	
	Y_cost = np.empty((1 << N,N), np.int64)
	Y_cost[0] = np.abs(Y) * P
	for n in range(N):
		B = 1 << n
		Y_cost[B:2 * B] = np.minimum(Y_cost[: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
		
		
		for _ in range(INF):
			u = s ^ t
			
			
			cost = (np.minimum(X_cost[t], Y_cost[u])).sum()
			ans[size] = min(ans[size], cost)
			if t == 0:
				break
			t = (t - 1) & s
	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)
 
	resolve = cc_export(resolve, (i8[:], ))
	cc.compile()
 
from my_module import resolve
 
N = int(readline())
XYP = np.array(read().split(), np.int64)
 
ans = resolve(XYP)
print('\n'.join(map(str, ans.tolist())))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]

table = [0] * N
for k in range(N): table[k] = min(abs(a[k][0]), abs(a[k][1])) * a[k][2]
tableudi = [10 ** 12 for _ in range((1 << N) * N)]
tablelri = [10 ** 12 for _ in range((1 << N) * N)]
for i in range(1 << N):
  for j in range(N):
    if i & (1 << j):
      for k in range(N):
        ud = min(abs(a[k][0] - a[j][0]) * a[k][2], table[k])
        lr = min(abs(a[k][1] - a[j][1]) * a[k][2], table[k])
        tableudi[i * N + k] = min(tableudi[i * N + k], ud)
        tablelri[i * N + k] = min(tablelri[i * N + k], lr)
    else:
      for k in range(N):
        tableudi[i * N + k] = min(tableudi[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
        tablelri[i * N + k] = min(tablelri[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
res = [10 ** 12] * (N + 1)
for t in range(1 << N):
  i = t + 0
  c = bin(t).count("1")
  while True:
    x = i + 0
    y = t ^ x
    rres = 0
    for j in range(N):
      rres += min(tableudi[x * N + j], tablelri[y * N + j])
    res[c] = min(res[c], rres)
    
    if i == 0: break
    i = (i - 1) & t
for r in res: print(r)

Solution (Python):



import sys
import numpy as np
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def resolve(XYP):
	X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
	N = len(X)
	X_cost = np.empty((1 << N,N), np.int64)
	X_cost[0] = np.abs(X) * P
	for n in range(N):
		B = 1 << n
		X_cost[B:2 * B] = np.minimum(X_cost[:B], np.abs((X-X[n]) * P))
	
	Y_cost = np.empty((1 << N,N), np.int64)
	Y_cost[0] = np.abs(Y) * P
	for n in range(N):
		B = 1 << n
		Y_cost[B:2 * B] = np.minimum(Y_cost[: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(X_cost[t], Y_cost[u])).sum()
			ans[size] = min(ans[size], cost)
			if t == 0:
				break
			t = (t - 1) & s
	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)
 
	resolve = cc_export(resolve, (i8[:], ))
	cc.compile()
 
from my_module import resolve

N = int(readline())
XYP = np.array(read().split(), np.int64)

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    li = []
    for _ in range(n):
        xi, yi, pi = map(int, input().split())
        li.append([xi, yi, pi])
    li.sort(key=lambda x: x[2], reverse=True)
    xx = [[abs(li[j][0]) for j in range(n)] for i in range(2**n)]
    yy = [[abs(li[j][1]) for j in range(n)] for i in range(2**n)]

    for i in range(2**n):
        X = [0]
        rest = []
        for j in range(n):
            if i >> j & 1 == 1:
                X.append(li[j][0])
                xx[i][j] = 0
            else:
                rest.append(j)
        for j in rest:
            res = 10**15
            for k in X:
                res = min(res, abs(li[j][0]-k))
            xx[i][j] = res

    for i in range(2**n):
        Y = [0]
        rest = []
        for j in range(n):
            if i >> j & 1 == 1:
                Y.append(li[j][1])
                yy[i][j] = 0
            else:
                rest.append(j)
        for j in rest:
            res = 10**15
            for k in Y:
                res = min(res, abs(li[j][1]-k))
            yy[i][j] = res

    index_list = [2**q for q in range(n)]
    klist = [10**15]*(n+1)
    klist[n] = 0
    xx=tuple(xx)
    yy=tuple(yy)

    for xyr2 in range(3**(n-1)):
        xyr = xyr2
        k, xopen, yopen = 0, 0, 0
        for index in range(n-1):
            xyr, num = divmod(xyr, 3)
            k += (num+1)//2
            xopen += (num % 2)*index_list[index]
            yopen += (num//2)*index_list[index]
        for app in range(3):
            k2, xopen2, yopen2 = k, xopen, yopen
            k2 += (app+1)//2
            xopen2 += (app % 2)*index_list[n-1]
            yopen2 += (app//2)*index_list[n-1]

            cost = 0
            for w in range(n):
                cost += min(xx[xopen2][w], yy[yopen2][w])*li[w][2]

            klist[k2] = min(klist[k2], cost)

    for g in range(n+1):
        print(klist[g])


if __name__ == '__main__':
    main()

Solution (Python):


import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():

    N = int(input())
    Resident = []
    for i in range(N):
        x,y,p = map(int,input().split())
        Resident.append((x,y,p))

    minCost = [float("inf")] * (N+1)

    preCalRange = 1 << N

    horizontalLineDistance = []
    verticalLineDistance = []

    for i in range(preCalRange):
        railRoad = bin(i)[2:]
        railRoad = '0' * (N - len(railRoad)) + railRoad
        horizontalLineDistance.append([])
        verticalLineDistance.append([])
        goodList1 = horizontalLineDistance[i]
        goodList2 = verticalLineDistance[i]
        for j in range(N):
            goodList1.append(min(abs(Resident[j][0]),abs(Resident[j][1])))
            goodList2.append(min(abs(Resident[j][0]),abs(Resident[j][1])))
            for k in range(N):
                if railRoad[k] == '1' and abs(Resident[j][0] - Resident[k][0]) < goodList1[j]:
                    goodList1[j] = abs(Resident[j][0] - Resident[k][0])
                if railRoad[k] == '1' and abs(Resident[j][1] - Resident[k][1]) < goodList2[j]:
                    goodList2[j] = abs(Resident[j][1] - Resident[k][1])

    loopCount = 1 << N
    for i in range(loopCount):
        numNewRailroad = bin(i)[2:].count('1')
        j = i
        while j >= 0:
            j &= i
            goodList1 = horizontalLineDistance[j]
            goodList2 = verticalLineDistance[i - j]
            cost = 0
            for k in range(N):
                cost += Resident[k][2] * min(goodList1[k], goodList2[k])
            if minCost[numNewRailroad] > cost:
                minCost[numNewRailroad] = cost
            j -= 1
    for elem in minCost:
        print(elem)

main()

Solution (Python):
import itertools

N = int(input())

data = []
min_value_0 = 0
for _ in range(N):
	X, Y, P = town = tuple(map(int, input().split()))
	data.append(town)
	min_value_0 += min(abs(X), abs(Y)) * P

print(min_value_0)

B = 2 ** N
table_h = []
table_v = []

for b in range(B):
	towns = []
	i = 0
	x = b
	while x > 0:
		if x % 2 == 1:
			towns.append(i)
		x //= 2
		i += 1
	dists_h = []
	dists_v = []
	for i in range(N):
		X0, Y0, P0 = data[i]
		d_h = abs(X0)
		d_v = abs(Y0)
		for j in towns:
			X1, Y1, P1 = data[j]
			d_h = min(d_h, abs(X1 - X0))
			d_v = min(d_v, abs(Y1 - Y0))
		dists_h.append(d_h * P0)
		dists_v.append(d_v * P0)
	table_h.append(dists_h)
	table_v.append(dists_v)


table = [min_value_0] * (N + 1)

import sys

stack = [0] * N
i = 0
c = 0
b0 = 0
b1 = 0
b = 1
while True:
	if i == N:
		value = 0
		t1 = table_h[b0]
		t2 = table_v[b1]
		for j in range(N):
			value += min(t1[j], t2[j])
		if table[c] > value:
			table[c] = value
		i -= 1
		b //= 2
	else:
		s = stack[i]
		if s == 3:
			if i == 0:
				break
			else:
				stack[i] = 0
				i -= 1
				b //= 2
		else:
			if s == 0:
				b0 += b
				c += 1
			elif s == 1:
				b0 -= b
				b1 += b
			else:
				b1 -= b
				c -= 1
			stack[i] = s + 1
			i += 1
			b *= 2

for i in range(1, N):
	print(table[i])

print(0)

Solution (Python):


import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():

    N = int(input())
    Resident = []
    for i in range(N):
        x,y,p = map(int,input().split())
        Resident.append((x,y,p))

    minCost = [float("inf")] * (N+1)

    preCalRange = 1 << N

    horizontalLineDistance = []
    verticalLineDistance = []

    for i in range(preCalRange):
        railRoad = bin(i)[2:]
        railRoad = '0' * (N - len(railRoad)) + railRoad
        horizontalLineDistance.append([])
        verticalLineDistance.append([])
        for j in range(N):
            horizontalLineDistance[i].append(min(abs(Resident[j][0]),abs(Resident[j][1])))
            verticalLineDistance[i].append(min(abs(Resident[j][0]),abs(Resident[j][1])))
            for k in range(N):
                if railRoad[k] == '1' and abs(Resident[j][0] - Resident[k][0]) < horizontalLineDistance[i][j]:
                    horizontalLineDistance[i][j] = abs(Resident[j][0] - Resident[k][0])
                if railRoad[k] == '1' and abs(Resident[j][1] - Resident[k][1]) < verticalLineDistance[i][j]:
                    verticalLineDistance[i][j] = abs(Resident[j][1] - Resident[k][1])

    loopCount = 1 << N
    for i in range(loopCount):
        numNewRailroad = bin(i)[2:].count('1')
        j = i
        while j >= 0:
            j &= i
            goodList1 = horizontalLineDistance[j]
            goodList2 = verticalLineDistance[i - j]
            cost = 0
            for k in range(N):
                cost += Resident[k][2] * min(goodList1[k], goodList2[k])
            if minCost[numNewRailroad] > cost:
                minCost[numNewRailroad] = cost
            j -= 1
    for elem in minCost:
        print(elem)

main()

Solution (Python):




import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():

    N = int(input())
    Resident = []
    for i in range(N):
        x,y,p = map(int,input().split())
        Resident.append((x,y,p))

    minCost = [float("inf")] * (N+1)

    preCalRange = 1 << N

    horizontalLineDistance = []
    verticalLineDistance = []

    for i in range(preCalRange):
        railRoad = bin(i)[2:]
        railRoad = '0' * (N - len(railRoad)) + railRoad
        horizontalLineDistance.append([])
        verticalLineDistance.append([])
        for j in range(N):
            horizontalLineDistance[i].append(min(abs(Resident[j][0]),abs(Resident[j][1])))
            verticalLineDistance[i].append(min(abs(Resident[j][0]),abs(Resident[j][1])))
            for k in range(N):
                if railRoad[k] == '1' and abs(Resident[j][0] - Resident[k][0]) < horizontalLineDistance[i][j]:
                    horizontalLineDistance[i][j] = abs(Resident[j][0] - Resident[k][0])
                if railRoad[k] == '1' and abs(Resident[j][1] - Resident[k][1]) < verticalLineDistance[i][j]:
                    verticalLineDistance[i][j] = abs(Resident[j][1] - Resident[k][1])

    power2 = [1]
    for i in range(N):
        power2.append(power2[-1] * 2)
    loopCount = power2[N]
    for i in range(loopCount):
        numNewRailroad = bin(i)[2:].count('1')
        j = i
        while j >= 0:
            j &= i
            goodList1 = horizontalLineDistance[j]
            goodList2 = verticalLineDistance[i - j]
            cost = 0
            for k in range(N):
                cost += Resident[k][2] * min(goodList1[k], goodList2[k])
            if minCost[numNewRailroad] > cost:
                minCost[numNewRailroad] = cost
            j -= 1
    for elem in minCost:
        print(elem)

main()