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):
n = int(input())
xyp = [list(map(int,input().split())) for i in range(n)]

def caldp(a):
    n = len(a)
    a.sort()
    dp = [[float("INF")]*(n+1) for i in range(n+1)]
    dp[0][0] = 0
    for l in range(n):
        for r in range(l+1,n+1):
            now = float("INF")
            for k in range(l,r):
                count = 0
                for i in range(l,r):
                    count += abs(a[i][0]-a[k][0])*a[i][1]
                    if count >= now:
                        break
                now = min(now,count)
            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 = [float("INF")]*(n+1)
    for i in range(n+1):
        res[i] = dp[-1][i]
    return res

ans = [float("INF")]*(n+1)

for s in range(1<<n):
    lx = []
    ly = []
    for i in range(n):
        if s >> i & 1:
            lx.append((xyp[i][0],xyp[i][2]))
        else:
            ly.append((xyp[i][1],xyp[i][2]))
    lx = caldp(lx)
    ly = caldp(ly)
    for i in range(len(lx)):
        for j in range(len(ly)):
            ans[i+j] = min(ans[i+j],lx[i]+ly[j])

for i in ans:
    print(i)

Solution (Python):
def main():
    n = int(input())
    xyp = [list(map(int,input().split())) for i in range(n)]

    def caldp(a):
        n = len(a)
        a.sort()
        dp = [[float("INF")]*(n+1) for i in range(n+1)]
        dp[0][0] = 0
        for l in range(n):
            for r in range(l+1,n+1):
                now = float("INF")
                for k in range(l,r):
                    count = 0
                    for i in range(l,r):
                        count += abs(a[i][0]-a[k][0])*a[i][1]

                    now = min(now,count)
                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 = [float("INF")]*(n+1)
        for i in range(n+1):
            res[i] = dp[-1][i]
        return res

    ans = [float("INF")]*(n+1)

    for s in range(1<<n):
        lx = []
        ly = []
        for i in range(n):
            if s >> i & 1:
                lx.append((xyp[i][0],xyp[i][2]))
            else:
                ly.append((xyp[i][1],xyp[i][2]))
        lx = caldp(lx)
        ly = caldp(ly)
        for i in range(len(lx)):
            for j in range(len(ly)):
                ans[i+j] = min(ans[i+j],lx[i]+ly[j])

    for i in ans:
        print(i)

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
xyp = [list(map(int,input().split())) for i in range(n)]

def caldp(a):
    n = len(a)
    a.sort()
    dp = [[float("INF")]*(n+1) for i in range(n+1)]
    dp[0][0] = 0
    for l in range(n):
        for r in range(l+1,n+1):
            now = float("INF")
            for k in range(l,r):
                count = 0
                for i in range(l,r):
                    count += abs(a[i][0]-a[k][0])*a[i][1]

                now = min(now,count)
            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 = [float("INF")]*(n+1)
    for i in range(n+1):
        res[i] = dp[-1][i]
    return res

ans = [float("INF")]*(n+1)

for s in range(1<<n):
    lx = []
    ly = []
    for i in range(n):
        if s >> i & 1:
            lx.append((xyp[i][0],xyp[i][2]))
        else:
            ly.append((xyp[i][1],xyp[i][2]))
    lx = caldp(lx)
    ly = caldp(ly)
    for i in range(len(lx)):
        for j in range(len(ly)):
            ans[i+j] = min(ans[i+j],lx[i]+ly[j])

for i in ans:
    print(i)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            xcal[i][j] *= l[j][2]
            ycal[i][j] *= l[j][2]
    ans = [float("INF")]*(n+1)

    for i in range(1<<n):
        count = 0
        for j in range(n):
            if i >> j & 1:
                count += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(n):
                if not (i>>k & 1):
                    cost += min(xcal[j][k],ycal[i-j][k])
                if cost > ans[count]:
                    break
            ans[count] = min(ans[count],cost)
            j -= 1

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
X, Y, P = [], [], []
for i in range(n):
    x, y, p = map(int, input().split())
    X.append(x)
    Y.append(y)
    P.append(p)

DX = [[0] * n for s in range(1 << n)]
DY = [[0] * n for s in range(1 << n)]
for s in range(1 << n):
    for i in range(n):
        DX[s][i] = abs(X[i]) * P[i]
        DY[s][i] = abs(Y[i]) * P[i]
        for j in range(n):
            if s & (1 << j):
                DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
                DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])

BC = [bin(s).count("1") for s in range(1 << n)]
A = [10**20] * (n + 1)
for sx in range(1 << n):
    rx = ((1 << n) - 1) ^ sx
    sy = rx
    for _ in range(1 << (n - BC[sx])):
        sy = (sy - 1) & rx
        d = 0
        for i in range(n):
            d += min(DX[sx][i], DY[sy][i])
        c = BC[sx] + BC[sy]
        A[c] = min(A[c], d)
print(*A, sep="\n")

Solution (Python):
n = int(input())
XYP = [tuple(map(int, input().split())) for i in range(n)]
X = [x for x, y, p in XYP]
Y = [y for x, y, p in XYP]
P = [p for x, y, p in XYP]
pow2 = [2**i for i in range(n + 1)]

DX = [[0] * n for s in range(pow2[n])]
DY = [[0] * n for s in range(pow2[n])]
for s in range(1 << n):
    for i in range(n):
        DX[s][i] = abs(X[i]) * P[i]
        DY[s][i] = abs(Y[i]) * P[i]
        for j in range(n):
            if s & (1 << j):
                DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
                DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])

BC = [bin(s).count("1") for s in range(pow2[n])]

A = [10**20] * (n + 1)
for sx in range(pow2[n]):
    rx = (pow2[n] - 1) ^ sx
    sy = rx
    for _ in range(pow2[n - BC[sx]]):
        sy = (sy - 1) & rx
        d = 0
        for i in range(n):
            d += min(DX[sx][i], DY[sy][i])
        c = BC[sx] + BC[sy]
        A[c] = min(A[c], d)
print(*A, sep="\n")

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i, (x, y, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = bin(i).count("1")
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i, (x, y, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    answer = [INF] * (N+1)
    count = 0
    for i in range(1 << N):
        cnt = bin(i).count("1")
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                count += 1
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
xyp=[list(map(int,input().split())) for i in range(n)]
cost=[10**20]*(1<<n)
cost[0]=0
for bitt in range(1,1<<n):
  xx=[]
  yy=[]
  pp=[]
  m=0
  for i in range(n):
    x,y,p=xyp[i]
    if (1<<i)&bitt:
      xx.append(x)
      yy.append(y)
      pp.append(p)
      m+=1
  for i in range(m):
    sx=xx[i]
    anss=0
    for x,y,p in zip(xx,yy,pp):
      anss+=min(abs(y),abs(x),abs(sx-x))*p
    cost[bitt]=min(cost[bitt],anss)
  for j in range(m):
    sy=yy[j]
    anss=0
    for x,y,p in zip(xx,yy,pp):
      anss+=min(abs(y),abs(x),abs(sy-y))*p
    cost[bitt]=min(cost[bitt],anss)
dp=[sum(min(abs(xyp[i][0]),abs(xyp[i][1]))*xyp[i][2] for i in range(n) if (1<<i)&j) for j in range(1<<n)]
print(dp[-1])
for j in range(n):
  for i in range((1<<n)-1,0,-1):
    x=i
    while x>=0:
      x&=i
      dp[i]=min(dp[i],dp[i-x]+cost[x])
      x-=1
  print(dp[-1])

Solution (Python):

import sys
rl = sys.stdin.buffer.readline
INF = sys.maxsize

N = int(rl())
PS = [tuple(map(int, rl().split())) for i in range(N)]

def bitcount(n):
  n = n - ((n >> 1) & 0x5555555555555555)
  n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
  n = (n + (n >> 4)) & 0x0f0f0f0f0f0f0f0f
  n = n + (n >> 8)
  n = n + (n >> 16)
  n = n + (n >> 32)
  return n & 0x0000007f

def subsets(s):
  t = s
  while t >= 0:
    t &= s
    yield t
    t -= 1


xcost = [[INF] * N for _ in range(1 << N)]
ycost = [[INF] * N for _ in range(1 << N)]
for i in range(1 << N):
  for j in range(N):
    xcost[i][j] = abs(PS[j][0])
    ycost[i][j] = abs(PS[j][1])
    for k in range(N):
      if ((i >> k) & 1) == 1:
        xcost[i][j] = min(xcost[i][j], abs(PS[j][0] - PS[k][0]))
        ycost[i][j] = min(ycost[i][j], abs(PS[j][1] - PS[k][1]))


for i in range(1 << N):
  for j in range(N):
    xcost[i][j] = xcost[i][j] * PS[j][2]
    ycost[i][j] = ycost[i][j] * PS[j][2]


ans = [INF] * (N + 1)
for i in range(1 << N):
  size = bitcount(i)
  for j in subsets(i):
    cost = 0
    for k in range(N):
      
      if ((i >> k) & 1) == 0:
        cost += min(xcost[j][k], ycost[i-j][k])

    ans[size] = min(ans[size], cost)


for a in ans:
  print(a)

Solution (Python):


import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    
    
    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i, (x, y, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        
        
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1
    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    
    
    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i, (x, y, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    
    
    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i in range(N):
            X_dist[bit][i] = T[i][2]*min(abs(cx - T[i][0]) for cx in cur_x)
            Y_dist[bit][i] = T[i][2]*min(abs(cy - T[i][1]) for cy in cur_y)

    
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        a, b, c = (int(i) for i in input().split())
        X.append(a)
        Y.append(b)
        P.append(c)
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    
    
    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(X[i])
                cur_y.append(Y[i])
        for i in range(N):
            X_dist[bit][i] = P[i]*min(abs(cx - X[i]) for cx in cur_x)
            Y_dist[bit][i] = P[i]*min(abs(cy - Y[i]) for cy in cur_y)

    
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        a, b, c = (int(i) for i in input().split())
        X.append(a)
        Y.append(b)
        P.append(c)
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    
    
    for bit in range(1 << N):
        for i in range(N):
            X_dist[bit][i] = P[i]*abs(X[i])
            Y_dist[bit][i] = P[i]*abs(Y[i])
            for k in range(N):
                if bit & (1 << k):
                    X_dist[bit][i] = \
                        min(X_dist[bit][i], P[i]*abs(X[i] - X[k]))
                    Y_dist[bit][i] = \
                        min(Y_dist[bit][i], P[i]*abs(Y[i] - Y[k]))

    
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):











def solve(N, X, Y, P):
    inf = 10 ** 18
    cnb_N = 2 ** N
    
    
    to_x = [[0] * N for _ in range(cnb_N)]
    to_y = [[0] * N for _ in range(cnb_N)]
    for cn in range(cnb_N):
        for n in range(N):
            to_x[cn][n] = abs(X[n]) * P[n]
            to_y[cn][n] = abs(Y[n]) * P[n]
            for n2 in range(N):
                if cn >> n2 & 1:
                    to_x[cn][n] = min(to_x[cn][n], abs(X[n] - X[n2]) * P[n])
                    to_y[cn][n] = min(to_y[cn][n], abs(Y[n] - Y[n2]) * P[n])

    
    
    ans = [inf] * (N + 1)
    for cn in range(cnb_N):
        count = 0
        for i in range(N):
            count += 1 if cn >> i & 1 else 0
        cn2 = cn
        while cn2 >= 0:
            cn2 = cn2 & cn
            subsum = 0
            for n in range(N):
                if not (cn >> n & 1):
                    subsum += min(to_x[cn - cn2][n], to_y[cn2][n])
            ans[count] = min(ans[count], subsum)
            cn2 -= 1

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


if __name__ == '__main__':
    
    N = int(input())
    
    X, Y, P = [], [], []
    for _ in range(N):
        tmp = [int(i) for i in input().split()]
        X.append(tmp[0])
        Y.append(tmp[1])
        P.append(tmp[2])
    solve(N, X, Y, P)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)


import bisect




INF = 1 << 50

def generate_dist_arr(X, Y, P):
    N = len(X)
    dist_arr_x = [[] for _ in range(1<<N)]
    dist_arr_y = [[] for _ in range(1<<N)]
    for j in range(1 << N):  
        x_lines_list = [0]
        y_lines_list = [0]
        for k in range(N):
            if j >> k & 1:
                x_lines_list.append(X[k])
                y_lines_list.append(Y[k])

        dist_xx, dist_yy = [INF] * N, [INF] * N
        x_lines_list = sorted(x_lines_list)
        y_lines_list = sorted(y_lines_list)
        for idx, x in enumerate(X):
            v = bisect.bisect_left(x_lines_list, x)
            pre_x = x_lines_list[min(v-1,  0)]
            post_x = x_lines_list[min(v, len(x_lines_list)-1)]
            dist_xx[idx] = min(abs(pre_x - x), abs(post_x - x)) * P[idx]
        dist_arr_x[j] = dist_xx

        for idx, y in enumerate(Y):
            v = bisect.bisect_left(y_lines_list, y)
            pre_y = y_lines_list[max(v-1, 0)]
            post_y = y_lines_list[min(v, len(y_lines_list) - 1)]
            dist_yy[idx] = min(abs(pre_y - y), abs(post_y - y)) * P[idx]
        dist_arr_y[j] = dist_yy
    return dist_arr_x, dist_arr_y

def calc(val_list):
    val_list = sorted(val_list)
    n = len(val_list)
    dp = [[INF] * (n+1) for _ in range(n+1)]
    dp[0][0] = 0

    for l in range(n+1):
        for r in range(l+1, n+1):
            next_dist = INF
            for k in range(l+1, r+1):
                sum = 0
                for v in range(l+1, r+1):
                    sum += abs(val_list[v-1][0] - val_list[k-1][0]) * val_list[v-1][1]
                next_dist = min(next_dist, sum)
            for j in range(n):
                dp[r][j + 1] = min(dp[r][j + 1], dp[l][j] + next_dist)
            
            sum = 0
            for v in range(l + 1, r + 1):
                sum += abs(val_list[v-1][0]) * val_list[v-1][1]
            next_dist = sum

            for j in range(n+1):
                dp[r][j] = min(dp[r][j], dp[l][j]+next_dist)
    return dp


def run():
    N = int(sysread())
    X, Y = [], []

    for i in range(1, N+1):
        x,y,p = map(int, sysread().split())
        X.append((x, p))
        Y.append((y, p))

    ans = [INF] * (N + 1)


    for i in range(1 << N):
        x_town_list = []
        y_town_list = []
        for k in range(N):
            if i >> k & 1:
                x_town_list.append(X[k])
            else:
                y_town_list.append(Y[k])
        
        
        dp_x = calc(x_town_list)[-1]
        dp_y = calc(y_town_list)[-1]
        
        
        
        
        

        for i in range(len(dp_x)):
            for j in range(len(dp_y)):
                val = dp_x[i] + dp_y[j]
                ans[i + j] = min(ans[i + j], val)


    for a in ans:
        print(a)


if __name__ == "__main__":
    run()

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    P = read_lists(N)
    
    
    
    C = [1 << 62] * (N + 1)
    
    
    CX = [1 << 62] * (N * 2 ** N)
    CY = [1 << 62] * (N * 2 ** N)

    LX = [0] * (2 ** N)
    LY = [0] * (2 ** N)
    for K in range(2 ** N):
        X = {0}
        Y = {0}
        for i in range(N):
            if (K >> i) & 1:
                X.add(P[i][0])
                Y.add(P[i][1])
         
        
        
        for j, (xp, yp, cp) in enumerate(P):
            for x in X:
                
                CX[K * N + j] = min(abs(xp - x) * cp, CX[K * N + j])
            for y in Y:
                CY[K * N + j] = min(abs(yp - y) * cp, CY[K * N + j])
                
            
        LX[K] = len(X)
        LY[K] = len(Y)
        
        

    for T in range(2 ** N):
        p = format(T, "160b").count("1")
        if C[p] == 0:
            continue

        r = 1 << 62
        tx = T
        while True:
            ty = T - tx
            c = 0
            for n in range(N):
                c += min(CX[tx * N + n], CY[ty * N + n])
            r = min(r, c)
            if tx == 0:
                break
            tx = (tx - 1) & T
        C[p] = min(C[p], r)
    print("\n".join(map(str, C)))


if __name__ == "__main__":
    main()

Solution (Python):
INF = 10 ** 12

N = int(input())
X = [0] * N
Y = [0] * N
P = [0] * N
for i in range(N):
    X[i], Y[i], P[i] = map(int,input().split())

score_X = []

for i in range(2 ** N):
    x = []
    I = i
    for j in range(N):
        i = I
        score = abs(X[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(X[j] - X[k]) * P[j])
            i >>= 1
        x.append(score)
    score_X.append(x)

score_Y = []

for i in range(2 ** N):
    y = []
    I = i
    for j in range(N):
        i = I
        score = abs(Y[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(Y[j] - Y[k]) * P[j])
            i >>= 1
        y.append(score)
    score_Y.append(y)

ans = [INF] * (N + 1)

for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
    
    j = i
    
    while True:
        score = 0
        for k in range(N):
            if not (i >> k) & 1:
                score += min(score_X[j][k], score_Y[i - j][k])
        ans[cnt] = min(ans[cnt], score)
        if j == 0:
            break
        j = (j - 1) & i

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

Solution (Python):
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement, product
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**12

    N = II()
    positions = deque()
    for i in range(N):
        positions.append(LMIIS())
    
    
    v = []
    h = []
    for i in range(2**N):
        v.append([INF]*N)
        h.append([INF]*N)
    for i in range(2**N):
        v_lines = deque([0])
        h_lines = deque([0])
        for j in range(N):
            if 2 ** j & i:
                v_lines.append(positions[j][0])
                h_lines.append(positions[j][1])
        for j,(x,y,p) in enumerate(positions):
            min_x = INF
            min_y = INF
            for x_c in v_lines:
                min_x = min(min_x, abs(x_c - x)*p)
            for y_c in h_lines:
                min_y = min(min_y, abs(y_c - y)*p)
            v[i][j] = min_x
            h[i][j] = min_y

    ans = [INF]*(N+1)
    
    n_bit_mask = (1<<N)-1
    for pattern in range(2**N):
        
        cities = [i for i in range(N) if 2**i&pattern==0]
        key = N - len(cities)
        

        pattern_v = pattern
        pattern_h = 0
        
        while True:
            sum_diff = 0
            for i in cities:
                sum_diff += min(v[pattern_v][i],h[pattern_h][i])
            ans[key] = min(ans[key], sum_diff)
            if pattern_v == 0:
                break
            pattern_v = (pattern_v-1)&pattern
            pattern_h = pattern - pattern_v
    print('\n'.join(map(str,ans)))





            



    

    



    
main()