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):
import numpy as np
from numba import njit, int64
import sys

read = sys.stdin.buffer.read


@njit((int64, int64[:], int64[:], ), cache=True)
def pre_calc(n, pos, coef):
    ret = np.empty((1 << n, n), np.int64)
    ret[0] = np.abs(pos) * coef

    for i in range(n):
        bt = 1 << i
        ret[bt:2 * bt] = np.minimum(ret[:bt], np.abs(pos - pos[i]) * coef)

    return ret


@njit((int64[:], ), cache=True)
def solve(inp):
    INF = 10 ** 18

    n = inp[0]
    x = inp[1::3]
    y = inp[2::3]
    p = inp[3::3]

    ver = pre_calc(n, x, p)
    hor = pre_calc(n, y, p)

    ans = [INF] * (n + 1)
    for i in range(pow(3, n)):
        vi = 0
        hi = 0
        cnt = 0
        pow2 = 1
        pow3 = i
        while pow3:
            pow3, r = divmod(pow3, 3)
            if r == 1:
                vi += pow2
                cnt += 1
            elif r == 2:
                hi += pow2
                cnt += 1

            pow2 *= 2

        score = np.minimum(ver[vi], hor[hi]).sum()
        ans[cnt] = min(ans[cnt], score)

    return ans


inp = np.array(read().split(), np.int64)
ans = solve(inp)
print(*ans, sep="\n")

Solution (Python):
import numpy as np
from numba import njit, int64
import sys

read = sys.stdin.buffer.read


@njit((int64[:], ), cache=True)
def solve(inp):
    INF = 10 ** 18

    n = inp[0]
    x = inp[1::3]
    y = inp[2::3]
    p = inp[3::3]

    ver = np.empty((1 << n, n), np.int64)
    ver[0] = np.abs(x) * p

    for i in range(n):
        bt = 1 << i
        ver[bt:2 * bt] = np.minimum(ver[:bt], np.abs(x - x[i]) * p)

    hor = np.empty((1 << n, n), np.int64)
    hor[0] = np.abs(y) * p

    for i in range(n):
        bt = 1 << i
        hor[bt:2 * bt] = np.minimum(hor[:bt], np.abs(y - y[i]) * p)

    ans = [INF] * (n + 1)
    for i in range(pow(3, n)):
        vi = 0
        hi = 0
        cnt = 0
        pow2 = 1
        pow3 = i
        while pow3:
            pow3, r = divmod(pow3, 3)
            if r == 1:
                vi += pow2
                cnt += 1
            elif r == 2:
                hi += pow2
                cnt += 1

            pow2 *= 2

        score = np.minimum(ver[vi], hor[hi]).sum()
        ans[cnt] = min(ans[cnt], score)

    return ans


inp = np.array(read().split(), np.int64)
ans = solve(inp)
print(*ans, sep="\n")

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from numba import njit, prange
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in prange(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from numba import njit, prange
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in prange(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in prange(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()

Solution (Python):
INF = float("inf")

N, *XYP = map(int, open(0).read().split())
XYP = list(zip(*[iter(XYP)] * 3))

def solve(XP):
    M = len(XP)
    XP.sort()

    dp = [[INF] * (M + 1) for _ in range(M + 1)]
    dp[0][0] = 0

    for i, (x, p) in enumerate(XP):
        dp[i + 1][0] = dp[i][0] + abs(x) * p

    for l, dpl in enumerate(dp[:M]):
        for r in range(l + 1, M + 1):
            val = INF
            for lx, _ in XP[l:r]:
                cur = 0
                for x, p in XP[l:r]:
                    cur += p * min(abs(x - lx), abs(x))
                val = min(val, cur)

            for i in range(1, M + 1):
                dp[r][i] = min(
                    dp[r][i],
                    val + dpl[i - 1]
                )

    res = [INF] * (N + 1)
    res[:M + 1] = dp[M]
    return res


A = [INF] * (N + 1)
for state in range(1 << N):
    XP, YP = [], []
    for i, (x, y, p) in enumerate(XYP):
        if (state >> i) & 1:
            XP.append((x, p))
        else:
            YP.append((y, p))

    X, Y = solve(XP), solve(YP)
    for i in range(N + 1):
        for j in range(N + 1 - i):
            A[i + j] = min(A[i + j], X[i] + Y[j])

for a in A:
    print(a)

Solution (Python):
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def cal(xp):
    res=[inf]*(n+1)
    xp.sort()
    m=len(xp)
    dp=[[inf]*(m+1) for _ in range(m+1)]
    dp[0][0]=0
    for l,(x,p) in enumerate(xp):
        dp[l+1][0]=dp[l][0]+abs(x)*p
    for l in range(m):
        dpl=dp[l]
        for r in range(l+1,m+1):
            dpr=dp[r]
            val=inf
            for lx,_ in xp[l:r]:
                cur=0
                for x,p in xp[l:r]:
                    cur+=min(abs(x-lx),abs(x))*p
                val=min(cur,val)
            for j in range(1,m+1):
                dpr[j]=min(dpr[j],dpl[j-1]+val)
    dpm=dp[m]
    for i in range(m+1):res[i]=dpm[i]
    return res

inf = 10 ** 16
n = II()
xyp = LLI(n)
ans=[inf]*(n+1)
for s in range(1<<n):
    xp=[]
    yp=[]
    for i,(x,y,p) in enumerate(xyp):
        if s>>i&1:xp.append((x,p))
        else:yp.append((y,p))
    xc=cal(xp)
    yc=cal(yp)
    for i in range(n+1):
        for j in range(n+1-i):
            ans[i+j]=min(ans[i+j],xc[i]+yc[j])

for a in ans:print(a)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    N = int(input().strip())
    XYP = np.empty((N, 3), dtype=np.int32)
    for i in range(N):
        XYP[i] = np.fromstring(input().strip(), sep=" ")
    return N, XYP


@njit
def solve(N, XYP, INF=10**18):
    ans = np.full(N+1, INF, dtype=np.int64)
    vcost = np.zeros((2**N, N), dtype=np.int32)
    hcost = np.zeros((2**N, N), dtype=np.int32)

    
    for intptn in range(2**N):
        for i in range(N):
            xi, yi, pi = XYP[i]
            v = abs(xi)
            h = abs(yi)
            for j in range(N):
                xj, yj, pj = XYP[j]
                if (intptn >> j) & 1 == 1:
                    v = min(v, abs(xj-xi))
                    h = min(h, abs(yj-yi))
            vcost[intptn, i] += v
            hcost[intptn, i] += h

    
    for intptn in range(3**N):
        
        p, intvptn, inthptn = intptn, 0, 0
        u = 0
        for i in range(N):
            if p % 3 == 1:
                intvptn += 1 << (N-i-1)
                u += 1
            elif p % 3 == 2:
                inthptn += 1 << (N-i-1)
                u += 1
            p //= 3
        s = 0
        for i in range(N):
            s += min(vcost[intvptn, i], hcost[inthptn, i]) * XYP[i, 2]
        ans[u] = min(ans[u], s)
    
    return ans


if __name__ == '__main__':
    inputs = read()
    ans = solve(*inputs)
    for a in ans:
        print(a)

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

xx = [ [ abs(city[j][0]) for j in range(N) ] for i in range(2**N) ]
yy = [ [ abs(city[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:
      X.append(city[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(city[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:
      Y.append(city[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(city[j][1]-k))
    yy[i][j] = res


ans = [10**15 for _ in range(N+1)]
for i in range(2**N):
  cond = i
  rest = [j for j in range(N) if (i>>j)&1==0]
  count = N-len(rest)

  while True:
    X = cond
    Y = i-cond
    temp = 0
    for j in rest:
      temp += min(xx[X][j], yy[Y][j])*city[j][2]
    ans[count] = min(ans[count], temp)
    if cond == 0:
      break
    else:
      cond = (cond-1)&i

for i in range(N+1):
  print(ans[i])

Solution (Python):
N=int(input())
city=[]
for i in range(N):
    x,y,p=map(int,input().split())
    city.append((x,y,p))
 
xx=[[abs(city[j][0]) for j in range(N)] for i in range(2**N)]
yy=[[abs(city[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(city[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(city[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(city[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(city[j][1]-k))
        yy[i][j]=res
 
ans=[10**15 for i in range(N+1)]
for i in range(2**N):
    cond=i
    rest=[j for j in range(N) if i>>j &1==0]
    count=N-len(rest)
    while True:
        X=cond
        Y=i-cond
        temp=0
        for j in rest:
            temp+=min(xx[X][j],yy[Y][j])*city[j][2]
        ans[count]=min(ans[count],temp)
        if cond==0:
            break
        else:
            cond=(cond-1)&i
 
for i in range(N+1):
    print(ans[i])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    xc = [[0] * n for _ in range(1 << n)]
    yc = [[0] * n for _ in range(1 << n)]
    for s in range(1 << n):
        xcs = xc[s]
        ycs = yc[s]
        for i, (x, y, p) in enumerate(xyp):
            xcost = abs(x)
            ycost = abs(y)
            for j, (lx, ly, _) in enumerate(xyp):
                if s >> j & 1 == 0: continue
                if abs(x - lx) < xcost: xcost = abs(x - lx)
                if abs(y - ly) < ycost: ycost = abs(y - ly)
            xcs[i] = xcost * p
            ycs[i] = ycost * p
    

    ans = [inf] * (n + 1)
    for s in range(1 << n):
        k = bin(s).count("1")
        xs = (1 << n) - 1
        while xs > 0:
            xs &= s
            xcs = xc[xs]
            ycs = yc[s - xs]
            cur = 0
            for i in range(n): cur += min(xcs[i], ycs[i])
            if cur < ans[k]: ans[k] = cur
            xs -= 1

    for a in ans: print(a)

inf = 10 ** 16
n = II()
xyp = LLI(n)

solve()

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
X = []
Y = []
P = []
for _ in range(N):
    x,y,p = map(int,readline().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>>j)&1:
                d = min(d,abs(x-xx))
        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>>j)&1:
                d = min(d,abs(y-yy))
        DY[k][i] = d * P[i]                                                

PC = [0]*(1<<N)
for i in range(1<<N):
    PC[i] = PC[i//2] + 1 if i % 2 else PC[i//2]

RA = []
for i in range(1<<N):
    t = []
    for j in range(N):
        if i>>j & 1:
            t.append(j)
    RA.append(t)

INF = 10**31
mm = (1 << N) - 1
ANS = [INF]*(N+1)

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

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

N=int(input())
P=[list(map(int,input().split())) for i in range(N)]
ANS=[1<<60]*(N+1)
ANS[-1]=0
DP1=[20000]*N

S=0
for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))
    S+=DP1[i]*p

ANS[0]=S

def dfs(DP,now,used):
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x))
            S+=DP2[i]*P[i][2]

        ANS[used+1]=min(ANS[used+1],S)
        dfs(DP2,next_town+1,used+1)

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y))
            S+=DP2[i]*P[i][2]

        ANS[used+1]=min(ANS[used+1],S)
        dfs(DP2,next_town+1,used+1)

dfs(DP1,0,0)

for i in range(1,N):
    ANS[i]=min(ANS[i],ANS[i-1])

print(*ANS)

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

N=int(input())
P=[list(map(int,input().split())) for i in range(N)]
ANS=[1<<60]*(N+1)
ANS[-1]=0

DP1=[20000]*N

S=0
for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))
    S+=DP1[i]*p

ANS[0]=S

def dfs(DP,now,used):
    if used==N-1:
        return
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x))
            S+=DP2[i]*P[i][2]

        
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(DP2,next_town+1,used+1)

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y))
            S+=DP2[i]*P[i][2]

        
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(DP2,next_town+1,used+1)

dfs(DP1,0,0)

for i in range(1,N):
    ANS[i]=min(ANS[i],ANS[i-1])

print(*ANS)

Solution (Python):
import os
import sys

import numpy as np


def solve(n, kd, precalc_x, precalc_y):
    ans = np.full(n + 1, 10 ** 18, dtype=np.int64)

    def get_cost(v, bit):
        cost = 0
        pcx = precalc_x[v]
        pcy = precalc_y[v ^ bit]
        for i in range(n):
            cost += min(pcx[i], pcy[i])
        return cost

    for bit in range(1 << n):
        k = kd[bit]
        v = bit
        while v:
            ans[k] = min(ans[k], get_cost(v, bit))
            v = (v - 1) & bit
        ans[k] = min(ans[k], get_cost(0, bit))

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8, i8[:], i8[:,:], i8[:,:])')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8, i8[:], i8[:,:], i8[:,:])', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
n = inp[0]
xxx = inp[1::3]
yyy = inp[2::3]
ppp = inp[3::3]

bit_d = (((np.arange(1 << n)[:, None] & (1 << np.arange(n)))) > 0).astype(np.int64)
precalc_x = abs((xxx[None, :] * bit_d)[..., None] - xxx[None, None, :]).min(axis=1) * ppp[None, :]
precalc_y = abs((yyy[None, :] * bit_d)[..., None] - yyy[None, None, :]).min(axis=1) * ppp[None, :]
kd = bit_d.sum(axis=1)

ans = solve(n, kd, precalc_x, precalc_y)
print('\n'.join(map(str, ans)))

Solution (Python):
import os
import sys

import numpy as np


def solve(n, precalc_x, precalc_y):
    ans = np.full(n + 1, 10 ** 18, dtype=np.int64)

    def get_cost(v, bit):
        cost = 0
        pcx = precalc_x[v]
        pcy = precalc_y[v ^ bit]
        for i in range(n):
            cost += min(pcx[i], pcy[i])
        return cost

    for bit in range(1 << n):
        k = (bit & 0x5555) + (bit >> 1 & 0x5555)
        k = (k & 0x3333) + (k >> 2 & 0x3333)
        k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
        k = (k & 0x00ff) + (k >> 8 & 0x00ff)
        v = bit
        while v:
            ans[k] = min(ans[k], get_cost(v, bit))
            v = (v - 1) & bit
        ans[k] = min(ans[k], get_cost(0, bit))

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8, i8[:,:], i8[:,:])')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8, i8[:,:], i8[:,:])', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
n = inp[0]
xxx = inp[1::3]
yyy = inp[2::3]
ppp = inp[3::3]

bit_d = (((np.arange(1 << n)[:, None] & (1 << np.arange(n)))) > 0).astype(np.int64)
precalc_x = abs((xxx[None, :] * bit_d)[..., None] - xxx[None, None, :]).min(axis=1) * ppp[None, :]
precalc_y = abs((yyy[None, :] * bit_d)[..., None] - yyy[None, None, :]).min(axis=1) * ppp[None, :]

ans = solve(n, precalc_x, precalc_y)
print('\n'.join(map(str, ans)))

Solution (Python):
import os
import sys

import numpy as np


def solve(n, precalc_x, precalc_y):
    ans = np.full(n + 1, 10 ** 18, dtype=np.int64)

    def get_cost(v, bit):
        cost = 0
        pcx = precalc_x[v]
        pcy = precalc_y[v ^ bit]
        for i in range(n):
            if v & (1 << i):
                continue
            cost += min(pcx[i], pcy[i])
        return cost

    for bit in range(1 << n):
        k = (bit & 0x5555) + (bit >> 1 & 0x5555)
        k = (k & 0x3333) + (k >> 2 & 0x3333)
        k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
        k = (k & 0x00ff) + (k >> 8 & 0x00ff)
        v = bit
        while v:
            ans[k] = min(ans[k], get_cost(v, bit))
            v = (v - 1) & bit
        ans[k] = min(ans[k], get_cost(0, bit))

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8, i8[:,:], i8[:,:])')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8, i8[:,:], i8[:,:])', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
n = inp[0]
xxx = inp[1::3]
yyy = inp[2::3]
ppp = inp[3::3]

bit_d = (((np.arange(1 << n)[:, None] & (1 << np.arange(n)))) > 0).astype(np.int64)
precalc_x = abs((xxx[None, :] * bit_d)[..., None] - xxx[None, None, :]).min(axis=1) * ppp[None, :]
precalc_y = abs((yyy[None, :] * bit_d)[..., None] - yyy[None, None, :]).min(axis=1) * ppp[None, :]

ans = solve(n, precalc_x, precalc_y)
print('\n'.join(map(str, ans)))

Solution (Python):
import os
import sys

import numpy as np


def solve(n, kd, precalc_x, precalc_y):
    ans = np.full(n + 1, 10 ** 18, dtype=np.int64)

    for bit in range(1 << n):
        k = kd[bit]
        v = bit
        while v:
            ans[k] = min(ans[k], np.minimum(precalc_x[v], precalc_y[v ^ bit]).sum())
            v = (v - 1) & bit
        ans[k] = min(ans[k], np.minimum(precalc_x[0], precalc_y[bit]).sum())

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8, i8[:], i8[:,:], i8[:,:])')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8, i8[:], i8[:,:], i8[:,:])', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
n = inp[0]
xxx = inp[1::3]
yyy = inp[2::3]
ppp = inp[3::3]

bit_d = (((np.arange(1 << n)[:, None] & (1 << np.arange(n)))) > 0).astype(np.int64)
precalc_x = abs((xxx[None, :] * bit_d)[..., None] - xxx[None, None, :]).min(axis=1) * ppp[None, :]
precalc_y = abs((yyy[None, :] * bit_d)[..., None] - yyy[None, None, :]).min(axis=1) * ppp[None, :]
kd = bit_d.sum(axis=1)

ans = solve(n, kd, precalc_x, precalc_y)
print('\n'.join(map(str, ans)))

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int, readline().split())
xyp = tuple(tuple(map(int, readline().split())) for _ in range(n))

N = 1<<n
INF = 1<<60
resx = []
resy = []
for i in range(n):
    x,y,p = xyp[i]
    rx = [abs(x)]*N
    ry = [abs(y)]*N
    for j in range(n):
        for k in range(1<<j):
            rx[k+(1<<j)] = min(rx[k],abs(x-xyp[j][0]))
            ry[k+(1<<j)] = min(ry[k],abs(y-xyp[j][1]))
    
    for j in range(N):
        rx[j] *= p
        ry[j] *= p
    resx.append(rx)
    resy.append(ry)

cnt = [n]*N
for j in range(n):
    for k in range(1<<j):
        cnt[k+(1<<j)] = cnt[k]-1

ans = [INF]*(n+1)
for m0 in range(N):
    v = cnt[m0]
    mx = (N-1)&~m0
    while mx>=0:
        my = (N-1)^m0^mx
        r = 0    
        for i in range(n):
            if m0>>i&1:
                r += min(resx[i][mx],resy[i][my])
        if r < ans[v]:
            ans[v] = r
        mx = (mx-1)&~m0


for i in ans:
    print(i)

Solution (Python):
import sys

n, *towns = map(int, sys.stdin.buffer.read().split())
xxx = towns[0::3]
yyy = towns[1::3]
ppp = towns[2::3]

INF = 10 ** 18
ans = [INF] * (n + 1)

precalc_dist_x = []
precalc_dist_y = []
for bit in range(1 << n):
    dists_x = []
    dists_y = []
    for i in range(n):
        x = xxx[i]
        y = yyy[i]
        dist_x = abs(x)
        dist_y = abs(y)

        t = bit
        j = 0
        while t:
            if t & 1:
                dist_x = min(dist_x, abs(xxx[j] - x))
                dist_y = min(dist_y, abs(yyy[j] - y))
            t >>= 1
            j += 1
        dists_x.append(dist_x * ppp[i])
        dists_y.append(dist_y * ppp[i])
    precalc_dist_x.append(dists_x)
    precalc_dist_y.append(dists_y)

for bit in range(1 << n):
    k = (bit & 0x5555) + (bit >> 1 & 0x5555)
    k = (k & 0x3333) + (k >> 2 & 0x3333)
    k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
    k = (k & 0x00ff) + (k >> 8 & 0x00ff)
    vertical = bit
    while vertical:
        cost = 0
        pcx = precalc_dist_x[vertical]
        pcy = precalc_dist_y[vertical ^ bit]
        for i in range(n):
            cost += min(pcx[i], pcy[i])
        ans[k] = min(ans[k], cost)
        vertical = (vertical - 1) & bit
    cost = 0
    pcx = precalc_dist_x[0]
    pcy = precalc_dist_y[bit]
    for i in range(n):
        cost += min(pcx[i], pcy[i])
    ans[k] = min(ans[k], cost)

print('\n'.join(map(str, ans)))

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int, readline().split())
xyp = tuple(tuple(map(int, readline().split())) for _ in range(n))

N = 1<<n
INF = 1<<60
resx = []
resy = []
for i in range(n):
    x,y,p = xyp[i]
    rx = [min(abs(x),abs(y))]*N
    ry = [min(abs(x),abs(y))]*N
    for j in range(n):
        for k in range(1<<j):
            rx[k+(1<<j)] = min(rx[k],abs(x-xyp[j][0]))
            ry[k+(1<<j)] = min(ry[k],abs(y-xyp[j][1]))
    
    for j in range(N):
        rx[j] *= p
        ry[j] *= p
    resx.append(rx)
    resy.append(ry)

ans = [INF]*(n+1)
N = 3**n

p = tuple(3**i for i in range(n+1))
rv = [0]*N
rx = [0]*N
ry = [0]*N
for j in range(n):
    for k in range(p[j]):
        rv[k+  p[j]] = rv[k+2*p[j]] = rv[k]
        rv[k] += 1

        rx[k+  p[j]] = rx[k]|(1<<j)
        ry[k+  p[j]] = ry[k]

        rx[k+2*p[j]] = rx[k]
        ry[k+2*p[j]] = ry[k]|(1<<j)

for mask in range(N):
    v = rv[mask]
    x = rx[mask]
    y = ry[mask]
    
    r = 0    
    for i in range(n):
        r += min(resx[i][x],resy[i][y])
    if r < ans[v]:
        ans[v] = r

for i in ans[::-1]:
    print(i)