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.



Sample input:
3
1 2 300
3 3 600
1 4 800


Sample output:
2900
900
0
0

Submission status: Time Limit Exceeded

Solution code:
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] * (1 << N) for _ in range(N)]
DY = [[0] * (1 << N) for _ in range(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[i][k] = 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[i][k] = d * P[i]
        
ANS = [1 << 100] * (N + 1)
PC = [0] * (1 << N)
for i in range(1, 1 << N):
    j = i ^ (i & (-i))
    PC[i] = PC[j] + 1
    
RA = []
for i in range(1 << N):
    t = []
    for j in range(N):
        if i & (1 << j):
            t.append(j)
    RA.append(tuple(t))
 
 
mm = (1 << N) - 1
for i in range(1 << N):
    m = i ^ mm
    j = m
    while 1:
        ans = 0
        for k in RA[i^j^mm]:
            ans += min(DX[k][i], DY[k][j])
        
        pc = PC[i] + PC[j]
        ANS[pc] = min(ANS[pc], ans)
        
        if not j:
            break
        j = m & (j - 1)

print(*ANS, sep = "\n")

Submission status: Time Limit Exceeded

Solution code:

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

ctr_x = [[0] * N for _ in range(2 ** N)]
ctr_y = [[0] * N for _ in range(2 ** N)]
for bit in range(2 ** N):
    for i in range(N):
        tmp_x = abs(X[i][0])
        tmp_y = abs(X[i][1])
        for j in range(N):
            if bit >> j & 1:
                tmp_x = min(tmp_x, abs(X[i][0] - X[j][0]))
                tmp_y = min(tmp_y, abs(X[i][1] - X[j][1]))

        ctr_x[bit][i] = tmp_x
        ctr_y[bit][i] = tmp_y

ans = [10 ** 12] * (N + 1)
for bit in range(2 ** N):
    cnt = bin(bit).count("1")
    for i in reversed(range(bit + 1)):
        i &= bit
        cost = 0
        for j in range(N):
            if not bit >> j & 1:
                cost += min(ctr_x[i][j], ctr_y[bit - i][j]) * X[j][2]
        ans[cnt] = min(ans[cnt], cost)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
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 
    
    for xyr2 in range(3**n):
        xyr = xyr2
        k,xopen,yopen=0,0,0
        for index in range(n):            
            num = xyr%3
            k+= (num+1)//2
            xopen += (num%2)*index_list[index]
            yopen += (num//2)*index_list[index]
            xyr//=3 

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

#前処理：集合に対して最適な路線を一つ選ぶO(N^2*2^N)
B = [0 for _ in range(2**N)]
for S_ in range(2**N):
  ans = 10 ** 20
  s = []
  i = 0
  S = S_
  while S > 0:
    if (S & 1):  
      s.append(i)
    S = S >> 1
    i += 1
  for k in s:
    #南北方向の路線の場合
    sm1 = 0
    for l in s:
      sm1 += abs(A[k][0] - A[l][0]) * A[l][2]
    #東西方向の路線の場合
    sm2 = 0
    for l in s:
      sm2 += abs(A[k][1] - A[l][1]) * A[l][2]
    ans = min(ans, sm1, sm2)
    #print(S_, s, ans, sm1, sm2)
    del sm1, sm2 
  if len(s) == 0:
    ans = 0
  B[S_] = ans    
  del ans, s
  
#Bit_DP... DP[S][i] = min{DP[S-T][i-1]+B[T]| T<S} 
DP = [[0 for _ in range(N+2)] for _ in range(2**N)] #0番目を南北、1番目を東西大通りとする

#南北大通りO(N*2^N)
for S_ in range(2**N):
  S = S_
  i = 0
  while S > 0:
    if (S & 1): 
      #print(i,S_,S,DP)
      DP[S_][0] += abs(A[i][0])*A[i][2]
    S = S >> 1
    i += 1
  #print(S_, DP[S_][0])

#東西大通りの下準備O(N*2^N)
C = [0 for _ in range(2**N)]
for S_ in range(2**N):
  S = S_
  i = 0
  while S > 0:
    if (S & 1):  
      C[S_] += abs(A[i][1])*A[i][2]
    S = S >> 1
    i += 1
  
#東西大通り
for S_ in range(2**N):
  #準備：S_の外延表記sを求める
  S = S_
  s = []
  i = 0
  while S > 0:
    if (S & 1):  
      s.append(i)
    S = S >> 1
    i += 1
  #print(s, S_)
  
  S = S_
  DP[S][1] = 10**20 
  #Sの部分集合を列挙して、DP[*][1]を実行
  for T_ in range(2**len(s)):
    T = T_
    i = 0
    L = 0
    while T > 0:
      if (T & 1):
        L += 2**s[i]
      T = T >> 1
      i += 1
    DP[S][1] = min(DP[S][1], DP[S-L][0] + C[L])
    #print(s,L, DP[S][1], DP[S-L][0] , C[L])
  DP[0][1] = 0


#DP[*][2~]を実行
for k in range(N): #DP[*][k+2]
  for S_ in range(2**N):
    #準備：Sの外延表記sを求める
    S = S_
    s = []
    i = 0
    while S > 0:
      if (S & 1):  
        s.append(i)
      S = S >> 1
      i += 1
  
    S = S_
    DP[S][k+2] = 10**20 
    #Sの部分集合を列挙して、DP[*][k+2]を実行
    for T_ in range(2**len(s)):
      T = T_
      i = 0
      L = 0
      while T > 0:
        if (T & 1):
          L += 2**s[i]
        T = T >> 1
        i += 1
      DP[S][k+2] = min(DP[S][k+2], DP[S-L][k+1] + B[L])
#print(B,C)   
#print(DP)
for k in range(-1,N):
  print(DP[2**N-1][k+2])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    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)
    import numpy as np
    # bit探索
    xcost = np.zeros((1 << n, n), dtype=int)
    ycost = np.zeros((1 << n, n), dtype=int)
    for i in range(1 << n):
        for j in range(n):
            xcost[i, j] = abs(X[j])
            ycost[i, j] = abs(Y[j])
            for k in range(n):
                if (i>>k)&1:
                    xcost[i, j] = min(xcost[i, j], abs(X[j]-X[k]))
                    ycost[i, j] = min(ycost[i, j], abs(Y[j]-Y[k]))
    xcost = xcost*P
    ycost = ycost*P
    inf = 1e18
    ans = np.full(n+1, inf, dtype=int)      
    for i in range(1 << n):
        cnt = format(i, 'b').count('1')
        for j in range(i, -1, -1):
            tmp = j&i
            if j!= 0 and tmp ==0:
                continue
            cost = 0
            for k in range(n):
                if not (i>>k)&1:
                    cost += min(xcost[tmp, k], ycost[i-tmp, k])
            ans[cnt] = min(ans[cnt], cost)
    for x in ans:
        print(x)

             
            
        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# Fast IO (only use in integer input)

# TLE

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

    def abs(N):
        if N >= 0:
            return N
        else:
            return -N

    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
            cost = 0
            for k in range(N):
                cost += Resident[k][2] * min(horizontalLineDistance[j][k], verticalLineDistance[i - j][k])
            if minCost[numNewRailroad] > cost:
                minCost[numNewRailroad] = cost
            j -= 1
    for elem in minCost:
        print(elem)

main()

Submission status: Time Limit Exceeded

Solution code:
# Fast IO (only use in integer input)

# TLE

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

    def abs(N):
        if N >= 0:
            return N
        else:
            return -N

    minCost = [-1] * (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] == -1 or minCost[numNewRailroad] > cost:
                minCost[numNewRailroad] = cost
            j -= 1
    for elem in minCost:
        print(elem)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *XYP = map(int, read().split())
    X = XYP[::3]
    Y = XYP[1::3]
    P = XYP[2::3]

    dist_x = [[0] * N for _ in range(1 << N)]
    dist_y = [[0] * N for _ in range(1 << N)]
    for i in range(1 << N):
        dx, dy = dist_x[i], dist_y[i]
        for j, (x, y) in enumerate(zip(X, Y)):
            dx[j], dy[j] = abs(x), abs(y)
            for k, (xk, yk) in enumerate(zip(X, Y)):
                if not (i & (1 << k)):
                    continue
                if dx[j] > abs(x - xk):
                    dx[j] = abs(x - xk)
                if dy[j] > abs(y - yk):
                    dy[j] = abs(y - yk)

    ans = [INF] * (N + 1)

    for i in range(1 << N):
        K = bin(i).count('1')
        for j in range(i, -1, -1):
            j &= i
            cost = 0
            for k, p in enumerate(P):
                if i & (1 << k):
                    continue
                cost += min(dist_x[j][k], dist_y[i - j][k]) * p

            if ans[K] > cost:
                ans[K] = cost

    print(*ans, sep='\n')

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# Fast IO (only use in integer input)

# TLE

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

    def abs(N):
        if N >= 0:
            return N
        else:
            return -N

    minCost = [-1] * (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])

    totalCases = 3 ** N
    power2 = [1]
    for i in range(N):
        power2.append(power2[-1] * 2)
    for i in range(1 << N):
        numNewRailroad = bin(i)[2:].count('1')
        for j in range(i,-1,-1):
            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] == -1 or minCost[numNewRailroad] > cost:
                minCost[numNewRailroad] = cost
    for elem in minCost:
        print(elem)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *XYP = map(int, read().split())
    X = XYP[::3]
    Y = XYP[1::3]
    P = XYP[2::3]

    dist_x = [[abs(x) for x in X] for _ in range(1 << N)]
    dist_y = [[abs(y) for y in Y] for _ in range(1 << N)]
    for i in range(1 << N):
        for j in range(N):
            if not i & (1 << j):
                continue
            for k, (x, y) in enumerate(zip(X, Y)):
                if dist_x[i][k] > abs(x - X[j]):
                    dist_x[i][k] = abs(x - X[j])
                if dist_y[i][k] > abs(y - Y[j]):
                    dist_y[i][k] = abs(y - Y[j])

    ans = [INF] * (N + 1)

    for i in range(1 << N):
        K = bin(i).count('1')
        for j in range(i, -1, -1):
            j &= i
            cost = 0
            for k, p in enumerate(P):
                if i & (1 << k):
                    continue
                cost += min(dist_x[j][k], dist_y[i - j][k]) * p

            if ans[K] > cost:
                ans[K] = cost

    print(*ans, sep='\n')

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)
#	print(f"{{:0{N}b}}".format(b), dist_h, dist_v)

table = [min_value_0] * (N + 1)

import sys

def calc(c, b0, b1, b, n):
	if n == N:
		value = 0
		t1 = table_h[b0]
		t2 = table_v[b1]
		for i in range(N):
			value += min(t1[i], t2[i])
		if table[c] > value:
			table[c] = value
	else:
		calc(c, b0, b1, b * 2, n + 1)
		calc(c + 1, b0 + b, b1, b * 2, n + 1)
		calc(c + 1, b0, b1 + b, b * 2, n + 1)

calc(0, 0, 0, 1, 0)

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

print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *XYP = map(int, read().split())
    X = XYP[::3]
    Y = XYP[1::3]
    P = XYP[2::3]

    dist_x = [[abs(x) for x in X] for _ in range(1 << N)]
    dist_y = [[abs(y) for y in Y] for _ in range(1 << N)]
    for i in range(1 << N):
        for j in range(N):
            if not i & (1 << j):
                continue
            for k, (x, y) in enumerate(zip(X, Y)):
                if dist_x[i][k] > abs(x - X[j]):
                    dist_x[i][k] = abs(x - X[j])
                if dist_y[i][k] > abs(y - Y[j]):
                    dist_y[i][k] = abs(y - Y[j])

    cost = [INF] * (N + 1)

    for i in range(1 << N):
        for j in range(i, -1, -1):
            j = i & j
            tmp = 0
            for k, p in enumerate(P):
                if i & (1 << k):
                    continue
                tmp += min(dist_x[j][k], dist_y[i - j][k]) * p

            K = bin(i).count('1')
            if cost[K] > tmp:
                cost[K] = tmp

    print(*cost, sep='\n')

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)
#	print(f"{{:0{N}b}}".format(b), dist_h, dist_v)

table = [min_value_0] * (N + 1)

import sys

for t in range(3 ** N):
	b0 = 0
	b1 = 0
	b = 1
	c = 0
	while t > 0:
		r = t % 3
		if r == 1:
			b0 += b
			c += 1
		elif r == 2:
			b1 += b
			c += 1
		b *= 2
		t //= 3
	value = 0
	t1 = table_h[b0]
	t2 = table_v[b1]
	for i in range(N):
		value += min(t1[i], t2[i])
	if table[c] > value:
		table[c] = value

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

print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *XYP = map(int, read().split())
    X = XYP[::3]
    Y = XYP[1::3]
    P = XYP[2::3]

    dist_x = [[abs(x) for x in X] for _ in range(1 << N)]
    dist_y = [[abs(y) for y in Y] for _ in range(1 << N)]
    for i in range(1 << N):
        for j in range(N):
            if not i & (1 << j):
                continue
            for k, (x, y) in enumerate(zip(X, Y)):
                if dist_x[i][k] > abs(x - X[j]):
                    dist_x[i][k] = abs(x - X[j])
                if dist_y[i][k] > abs(y - Y[j]):
                    dist_y[i][k] = abs(y - Y[j])

    cost = [INF] * (N + 1)

    def dfs(n, k, rail_x, rail_y):
        if n == N:
            ans = 0
            rx = int(''.join(map(str, reversed(rail_x))), 2)
            ry = int(''.join(map(str, reversed(rail_y))), 2)
            dx, dy = dist_x[rx], dist_y[ry]
            for i, p in enumerate(P):
                ans += min(dx[i], dy[i]) * p
            if cost[k] > ans:
                cost[k] = ans
            return

        dfs(n + 1, k, rail_x, rail_y)

        rail_x[n] = 1
        dfs(n + 1, k + 1, rail_x, rail_y)
        rail_x[n] = 0

        rail_y[n] = 1
        dfs(n + 1, k + 1, rail_x, rail_y)
        rail_y[n] = 0

        return

    dfs(0, 0, [0] * 15, [0] * 15)

    print(*cost, sep='\n')

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *XYP = map(int, read().split())
    X = XYP[::3]
    Y = XYP[1::3]
    P = XYP[2::3]

    dist_x = [[abs(x) for x in X] for _ in range(1 << N)]
    dist_y = [[abs(y) for y in Y] for _ in range(1 << N)]
    for i in range(1 << N):
        for j in range(N):
            if not i & (1 << j):
                continue
            for k, (x, y) in enumerate(zip(X, Y)):
                if dist_x[i][k] > abs(x - X[j]):
                    dist_x[i][k] = abs(x - X[j])
                if dist_y[i][k] > abs(y - Y[j]):
                    dist_y[i][k] = abs(y - Y[j])

    cost = [INF] * (N + 1)

    def dfs(n, k, rail_x, rail_y):
        if n == N:
            ans = 0
            dx, dy = dist_x[rail_x], dist_y[rail_y]
            for i, p in enumerate(P):
                ans += min(dx[i], dy[i]) * p
            if cost[k] > ans:
                cost[k] = ans
            return

        dfs(n + 1, k, rail_x, rail_y)
        dfs(n + 1, k + 1, rail_x + (1 << n), rail_y)
        dfs(n + 1, k + 1, rail_x, rail_y + (1 << n))
        return

    dfs(0, 0, 0, 0)

    print(*cost, sep='\n')

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product
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])
    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

    klist = [10**15]*(n+1)
    for xyr in list(product([0, 1, 2], repeat=n)):
        xopen = 0
        yopen = 0
        k = 0
        for index, num in enumerate(xyr):
            xopen += num*(2-num)*2**index
            yopen += (num*(num-1)*2**index)//2
            k += ((num-1)*(2-num)+2)//2
        if klist[k] == 0:
            continue
        cost = 0
        for w in range(n):
            cost += min(xx[xopen][w], yy[yopen][w])*li[w][2]

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *XYP = map(int, read().split())
    X = XYP[::3]
    Y = XYP[1::3]
    P = XYP[2::3]

    dist_x = [[abs(x) for x in X] for _ in range(1 << N)]
    dist_y = [[abs(y) for y in Y] for _ in range(1 << N)]
    for i in range(1 << N):
        for j in range(N):
            if not i & (1 << j):
                continue
            for k, (x, y) in enumerate(zip(X, Y)):
                if dist_x[i][k] > abs(x - X[j]):
                    dist_x[i][k] = abs(x - X[j])
                if dist_y[i][k] > abs(y - Y[j]):
                    dist_y[i][k] = abs(y - Y[j])

    cost = [INF] * (N + 1)

    def dfs(n, k, rail_x, rail_y):
        if n == N:
            ans = 0
            for i, p in enumerate(P):
                ans += min(dist_x[rail_x][i], dist_y[rail_y][i]) * p
            if cost[k] > ans:
                cost[k] = ans
            return

        dfs(n + 1, k, rail_x, rail_y)
        dfs(n + 1, k + 1, rail_x + (1 << n), rail_y)
        dfs(n + 1, k + 1, rail_x, rail_y + (1 << n))
        return

    dfs(0, 0, 0, 0)

    print(*cost, sep='\n')

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)
#	print(f"{{:0{N}b}}".format(b), dist_h, dist_v)

table = [min_value_0] * (N + 1)

import sys

for t in range(3 ** N):
	b0 = 0
	b1 = 0
	b = 1
	c = 0
	while t > 0:
		if t % 3 == 1:
			b0 += b
			c += 1
		elif t % 3 == 2:
			b1 += b
			c += 1
		b *= 2
		t //= 3
	value = 0
	for v0, v1 in zip(table_h[b0], table_v[b1]):
		value += min(v0, v1)
	if table[c] > value:
		table[c] = value

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

print(0)