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: Runtime Error

Solution code:
#解法１

#入力
N = int(input())
town = [list(map(int,input().split())) for i in range(N)]

#縦と横のリストを作る
vert = [town[i][0] for i in range(N)]
hori = [town[i][1] for i in range(N)]

#bit全探索
dX = []
for i in range(2**N):
    vertsel = []
    dXconst = [abs(town[l][0])*town[l][2] for l in range(N)]
    for j in range(N):
        if ((i >> j) & 1):
            vertsel.append(town[j][0])
    for k in vertsel:
        dXconst = [min(dXconst[l],abs(town[l][0]-k)*town[l][2]) for l in range(N)]
    dX.append(dXconst)

dY = []
for i in range(2**N):
    horisel = []
    dYconst = [abs(town[l][1])*town[l][2] for l in range(N)]
    for j in range(N):
        if ((i >> j) & 1):
            horisel.append(town[j][1])
    for k in horisel:
        dYconst = [min(dYconst[l],abs(town[l][1]-k)*town[l][2]) for l in range(N)]
    dY.append(dYconst)

#print('len(dX) ==',len(dX))
#print('len(dY) ==',len(dY))
#print(dX)
#print(dY)

#歩行距離を3進数を使って求める
ans = [float('inf') for K in range(N+1)]
for i in range(2**N):
    #print(i)
    Xvalue = 0
    Yvalue = 0
    K = 0
    #print('i ==',i)
    for j in range(N):
        if ((i >> j) & 1):
            K += 1
    for j in reversed(range(i+1)):
        j = (j&i)
        cost = 0
        for k in range(N):
            if not ((i >> k) & 1):
                cost += min(xsel[j][k], ysel[i-j][k])*town[k][2]
    ans[K] = min(sum([min(dX[Xvalue][l],dY[Yvalue][l]) for l in range(N)]),ans[K])

#出力
[print(ans[K]) for K in range(N+1)]

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

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

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

default_dist = np.minimum(np.abs(xxx), np.abs(yyy))

# どの点に線を引くか全探索
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)

    i = 0
    cur = 0
    t = bit
    # selected: 選択する点のidを格納
    selected = np.zeros(k, dtype=np.int)
    # is_selected: bit
    is_selected = np.zeros(k, dtype=np.int)
    while t:
        if t & 1:
            selected[cur] = i
            is_selected[i] = 1
            cur += 1
        t >>= 1
        i += 1

    # 引くと決めた座標にタテヨコどちらを引くか全探索
    for bit2 in range(1 << k):
        cost = 0
        for i in range(n):
            if is_selected[i]:
                continue
            town_dist = default_dist[i]
            t = bit2
            for j in range(k):
                if t & 1:
                    town_dist = min(town_dist, abs(yyy[selected[j]] - yyy[i]))
                else:
                    town_dist = min(town_dist, abs(xxx[selected[j]] - xxx[i]))
                t >>= 1
            cost += town_dist * ppp[i]
        ans[k] = min(ans[k], cost)


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

Submission status: Runtime Error

Solution code:
from itertools import product
import bisect
import sys
input = sys.stdin.readline
import numpy as np

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)
X = np.array(X).astype(np.int64)
Y = np.array(Y).astype(np.int64)
P = np.array(P).astype(np.int64)

ans = np.ones(2*n+1) * np.inf

vcosttable = [0] * (i<<n)
hcosttable = [0] * (i<<n)
vcdef = np.abs(X*P)
hcdef = np.abs(Y*P)
for bit in range(i<<n):
    vcost = np.copy(vcdef)
    hcost = np.copy(hcdef)
    for i in range(n):
        if bit & 1<<i:
            for j in range(n):
                vcost[j] = min(vcost[j], abs(X[j]-X[i])*P[j])
                hcost[j] = min(hcost[j], abs(Y[j]-Y[i])*P[j])
    vcosttable[bit] = vcost
    hcosttable[bit] = hcost

for choice in product([0, 1, 2], repeat=n):
    vbit, hbit = 0, 0
    NS, WE = set(), set()
    for i, c in enumerate(choice):
        if c == 0:
            # 選ばない
            continue
        elif c == 1:
            # 南北に引く
            vbit += 1<<i
            NS.add(X[i])
        else:
            # 東西に引く
            hbit += 1<<i
            WE.add(Y[i])
    line = len(NS)+len(WE)
    if line >= n: continue
    temp = np.sum(np.minimum(vcosttable[vbit], hcosttable[hbit]))
    ans[line] = min(ans[line], temp)
ans = ans.astype(np.int64)
for a in ans[:n+1]:
    print(a)

Submission status: Runtime Error

Solution code:
from itertools import product
import bisect
import sys
input = sys.stdin.readline
import numpy as np

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)
X = np.array(X).astype(np.int64)
Y = np.array(Y).astype(np.int64)
P = np.array(P).astype(np.int64)

ans = np.ones(2*n+1) * np.inf

vcosttable = [0] * (i<<n)
hcosttable = [0] * (i<<n)
vcdef = np.abs(X*P)
hcdef = np.abs(Y*P)
for bit in range(i<<n):
    vcost = np.copy(vcdef)
    hcost = np.copy(hcdef)
    for i in range(n):
        if bit & 1<<i:
            for j in range(n):
                vcost[j] = min(vcost[j], abs(X[j]-X[i])*P[j])
                hcost[j] = min(hcost[j], abs(Y[j]-Y[i])*P[j])
    vcosttable[bit] = vcost
    hcosttable[bit] = hcost

for choice in product([0, 1, 2], repeat=n):
    vbit, hbit = 0, 0
    NS, WE = set(), set()
    for i, c in enumerate(choice):
        if c == 0:
            # 選ばない
            continue
        elif c == 1:
            # 南北に引く
            vbit += 1<<i
            NS.add(X[i])
        else:
            # 東西に引く
            hbit += 1<<i
            WE.add(Y[i])
    line = len(NS)+len(WE)
    if line >= n: continue
    temp = np.sum(np.minimum(vcosttable[vbit], hcosttable[hbit]))
    ans[line] = min(ans[line], temp)
ans = ans.astype(np.int64)
for a in ans[:n]:
    print(a)

Submission status: Runtime Error

Solution code:
from itertools import product
import bisect
import sys
input = sys.stdin.readline
import numpy as np

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)
X = np.array(X).astype(np.int64)
Y = np.array(Y).astype(np.int64)
P = np.array(P).astype(np.int64)

ans = np.ones(2*n+1) * np.inf

vcosttable = [0] * (i<<n)
hcosttable = [0] * (i<<n)
vcdef = np.abs(X*P)
hcdef = np.abs(X*P)
for bit in range(i<<n):
    vcost = np.copy(vcdef)
    hcost = np.copy(hcdef)
    for i in range(n):
        if bit & 1<<i:
            for j in range(n):
                vcost[j] = min(vcost[j], abs(X[j]-X[i])*P[j])
                hcost[j] = min(hcost[j], abs(Y[j]-Y[i])*P[j])
    vcosttable[bit] = vcost
    hcosttable[bit] = hcost

for choice in product([0, 1, 2], repeat=n):
    vbit, hbit = 0, 0
    NS, WE = set(), set()
    for i, c in enumerate(choice):
        if c == 0:
            # 選ばない
            continue
        elif c == 1:
            # 南北に引く
            vbit += 1<<i
            NS.add(X[i])
        else:
            # 東西に引く
            hbit += 1<<i
            WE.add(Y[i])
    line = len(NS)+len(WE)
    if line >= n: continue
    temp = np.sum(np.minimum(vcosttable[vbit], hcosttable[hbit]))
    ans[line] = min(ans[line], temp)
ans = ans.astype(np.int64)
for a in ans[:n]:
    print(a)

Submission status: Runtime Error

Solution code:
from itertools import product
import bisect
import sys
input = sys.stdin.readline

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)

ans = [float('inf')] * (n+1)

vcosttable = [0] * (i<<n)
hcosttable = [0] * (i<<n)
for bit in range(i<<n):
    vcost = [abs(X[i]*P[i]) for i in range(n)]
    hcost = [abs(Y[i]*P[i]) for i in range(n)]
    for i in range(n):
        if bit & 1<<i:
            for j in range(n):
                vcost[j] = min(vcost[j], abs(X[j]-X[i])*P[j])
                hcost[j] = min(hcost[j], abs(Y[j]-Y[i])*P[j])
    vcosttable[bit] = vcost
    hcosttable[bit] = hcost

for choice in product([0, 1, 2], repeat=n):
    vbit, hbit = 0, 0
    NS, WE = set(), set()
    for i, c in enumerate(choice):
        if c == 0:
            # 選ばない
            continue
        elif c == 1:
            # 南北に引く
            vbit += 1<<i
            NS.add(X[i])
        else:
            # 東西に引く
            hbit += 1<<i
            WE.add(Y[i])
    line = len(NS)+len(WE)
    temp = 0
    for i in range(n):
        temp += min(vcosttable[vbit][i], hcosttable[hbit][i])
    ans[line] = min(ans[line], temp)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
aerfeaf

Submission status: Runtime Error

Solution code:
import sys
import itertools
import operator


def calc_distance(xyp, x_lines, y_lines):
    return sum(p * min(itertools.chain(
        (abs(x - v) for v in x_lines),
        (abs(y - v) for v in y_lines),
        )) for x, y, p in xyp)


def resolve(in_, out):
    n = int(next(in_))
    xyp = tuple(tuple(map(int, (line.split()))) for line in in_)

    print(calc_distance(xyp, [0], [0]), file=out)

    x_all_lines = frozenset(('x', x) for x, y, p in xyp if x != 0)
    y_all_lines = frozenset(('y', y) for x, y ,p in xyp if y != 0)
    all_lines = x_all_lines | y_all_lines
    for i in range(1, n + 1):
        d = []
        if i == 1:
            center = set()
            v = sorted(x for x, y, p in xyp if x != 0)
            center.add(('x', v[len(v) // 2]))
            if len(v) % 2:
                center.add(('x', v[len(v) // 2 + 1]))
            v = sorted(y for x, y, p in xyp if y != 0)
            center.add(('y', v[len(v) // 2]))
            if len(v) % 2:
                center.add(('y', v[len(v) // 2 + 1]))
            del v
            lines_combinations = all_lines | center
        else:
            lines_combinations = all_lines
        if len(lines_combinations) > i:
            lines_combinations = itertools.combinations(lines_combinations, i)

        for lines in lines_combinations:
            x_lines = [0]
            y_lines = [0]
            for line in lines:
                if line[0] == 'x':
                    x_lines.append(line[1])
                else:
                    y_lines.append(line[1])
            d.append(calc_distance(xyp, x_lines, y_lines))
        print(min(d, default=0), file=out)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import itertools
import operator


def calc_distance(xyp, x_lines, y_lines):
    return sum(p * min(itertools.chain(
        (abs(x - v) for v in x_lines),
        (abs(y - v) for v in y_lines),
        )) for x, y, p in xyp)


def resolve(in_, out):
    n = int(next(in_))
    xyp = tuple(tuple(map(int, (line.split()))) for line in in_)

    print(calc_distance(xyp, [0], [0]), file=out)

    x_all_lines = frozenset(('x', x) for x, y, p in xyp if x != 0)
    y_all_lines = frozenset(('y', y) for x, y ,p in xyp if y != 0)
    all_lines = x_all_lines | y_all_lines
    for i in range(1, n + 1):
        d = []
        if i == 1:
            v = sorted(x for x, y, p in xyp if x != 0)
            center = set((('x', v[len(v) // 2]),))
            if len(v) % 2:
                center.add(('x', v[len(v) // 2 + 1]))
            v = sorted(y for x, y, p in xyp if y != 0)
            center = set((('y', v[len(v) // 2]),))
            if len(v) % 2:
                center.add(('y', v[len(v) // 2 + 1]))
            del v
            line_combinations = itertools.combinations(all_lines | center, i)
        else:
            line_combinations = itertools.combinations(all_lines, i)
        for lines in line_combinations:
            x_lines = [0]
            y_lines = [0]
            for line in lines:
                if line[0] == 'x':
                    x_lines.append(line[1])
                else:
                    y_lines.append(line[1])
            d.append(calc_distance(xyp, x_lines, y_lines))
        print(min(d, default=0), file=out)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys


def main():

    N = int(sys.stdin.readline().rstrip())
    X, Y, P = [], [], []
    for i in range(N):
        x, y, p = map(int, sys.stdin.readline().rstrip().split())
        X.append(x)
        Y.append(y)
        P.append(p)

    st = time.time()
    # 前処理 2**15パターンの歩行距離
    hokou_X = [[0] * (2**N) for _ in range(N)]
    hokou_Y = [[0] * (2**N) for _ in range(N)]

    for i in range(2**N):
        for n in range(N):
            min_hokou_x_n = abs(X[n])
            min_hokou_y_n = abs(Y[n])
            for shift in range(N):
                if (i >> shift) & 1 == 1:
                    min_hokou_x_n = min(abs(X[n] - X[shift]), min_hokou_x_n)  # もっと近ければ更新
                    min_hokou_y_n = min(abs(Y[n] - Y[shift]), min_hokou_y_n)  # もっと近ければ更新
            hokou_X[n][i] += min_hokou_x_n * P[n]
            hokou_Y[n][i] += min_hokou_y_n * P[n]

    # print(hokou_X)
    # print(hokou_Y)

    hokou = [20000 * 15 * max(P)] * (N + 1)

    # 縦、横、なし　の3パターンを計算
    for i in range(3**N):

        if i % 100000 == 0:
            print(i)

        pt = i % (3**(n + 1)) // 3**n

        honsuu = 0
        xi = 0
        yi = 0
        # 路線の引き方を確認する
        for n in range(N):
            if pt == 1:  # 縦を使う
                xi += 2**n
                honsuu += 1
            if pt == 2:  # 横を使う
                yi += 2**n
                honsuu += 1

        # この路線の引き方の場合の最小値を考える
        hokou_tmp = 0
        for n in range(N):
            hokou_tmp += min(hokou_X[n][xi], hokou_Y[n][yi])

        hokou[honsuu] = min(hokou_tmp, hokou[honsuu])

    for i in hokou:
        print(i)

main()

Submission status: Runtime Error

Solution code:
# 写経
# https://atcoder.jp/contests/m-solutions2020/submissions/15454214

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

def resolve():
	X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
	N = len(X)
	X_cost = np.empty((1 << N,N), np.int64)
	X_cost[0] = np.abs(X) * P
	for n in range(N):
		B = 1 << n
		X_cost[B:2 * B] = np.minimum(X_cost[:B], np.abs((X-X[n]) * P))
	#print(X_cost)
	Y_cost = np.empty((1 << N,N), np.int64)
	Y_cost[0] = np.abs(Y) * P
	for n in range(N):
		B = 1 << n
		Y_cost[B:2 * B] = np.minimum(Y_cost[:B], np.abs((Y-Y[n]) * P))
	#print(Y_cost)
	popcount = np.zeros(1 << N, np.int64)
	for n in range(N):
		popcount[1 << n:1 << n + 1] = popcount[:1 << n] + 1
	#print(popcount)

	INF = 10**18
	ans = np.full(N + 1, INF, np.int64)
	for s in range(1 << N):
		size = popcount[s]
		t = s
		#print("s" + str(s))
		#print("size" + str(size))
		while True:
			u = s ^ t
			#print("u" + str(u))
			#print("t" + str(t))
			cost = (np.minimum(X_cost[t], Y_cost[u])).sum()
			ans[size] = min(ans[size], cost)
			if t == 0:
				break
			t = (t - 1) & s
	return ans 

if sys.argv[-1] == 'ONLINE_JUDGE':
	import numba
	from numba.pycc import CC
	i8 = numba.int64
	cc = CC('my_module')
 
	def cc_export(f, signature):
		cc.export(f.__name__, signature)(f)
		return numba.njit(f)
 
	resolve = cc_export(resolve, (i8[:], ))
	cc.compile()
 
from my_module import resolve

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

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

Submission status: Runtime Error

Solution code:
# 写経
# https://atcoder.jp/contests/m-solutions2020/submissions/15454214

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

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

def resolve():
	X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
	N = len(X)
	X_cost = np.empty((1 << N,N), np.int64)
	X_cost[0] = np.abs(X) * P
	for n in range(N):
		B = 1 << n
		X_cost[B:2 * B] = np.minimum(X_cost[:B], np.abs((X-X[n]) * P))
	#print(X_cost)
	Y_cost = np.empty((1 << N,N), np.int64)
	Y_cost[0] = np.abs(Y) * P
	for n in range(N):
		B = 1 << n
		Y_cost[B:2 * B] = np.minimum(Y_cost[:B], np.abs((Y-Y[n]) * P))
	#print(Y_cost)
	popcount = np.zeros(1 << N, np.int64)
	for n in range(N):
		popcount[1 << n:1 << n + 1] = popcount[:1 << n] + 1
	#print(popcount)

	INF = 10**18
	ans = np.full(N + 1, INF, np.int64)
	for s in range(1 << N):
		size = popcount[s]
		t = s
		#print("s" + str(s))
		#print("size" + str(size))
		while True:
			u = s ^ t
			#print("u" + str(u))
			#print("t" + str(t))
			cost = (np.minimum(X_cost[t], Y_cost[u])).sum()
			ans[size] = min(ans[size], cost)
			if t == 0:
				break
			t = (t - 1) & s
	for Ans in ans:
		print(Ans)

if sys.argv[-1] == 'ONLINE_JUDGE':
	import numba
	from numba.pycc import CC
	i8 = numba.int64
	cc = CC('my_module')
 
	def cc_export(f, signature):
		cc.export(f.__name__, signature)(f)
		return numba.njit(f)
 
	resolve = cc_export(resolve, (i8[:], ))
	cc.compile()
 
from my_module import resolve

resolve()

Submission status: Runtime Error

Solution code:
# 写経
# https://atcoder.jp/contests/m-solutions2020/submissions/15454214

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

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

def resolve():
	X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
	N = len(X)
	X_cost = np.empty((1 << N,N), np.int64)
	X_cost[0] = np.abs(X) * P
	for n in range(N):
		B = 1 << n
		X_cost[B:2 * B] = np.minimum(X_cost[:B], np.abs((X-X[n]) * P))
	#print(X_cost)
	Y_cost = np.empty((1 << N,N), np.int64)
	Y_cost[0] = np.abs(Y) * P
	for n in range(N):
		B = 1 << n
		Y_cost[B:2 * B] = np.minimum(Y_cost[:B], np.abs((Y-Y[n]) * P))
	#print(Y_cost)
	popcount = np.zeros(1 << N, np.int64)
	for n in range(N):
		popcount[1 << n:1 << n + 1] = popcount[:1 << n] + 1
	#print(popcount)

	INF = 10**18
	ans = np.full(N + 1, INF, np.int64)
	for s in range(1 << N):
		size = popcount[s]
		t = s
		#print("s" + str(s))
		#print("size" + str(size))
		while True:
			u = s ^ t
			#print("u" + str(u))
			#print("t" + str(t))
			cost = (np.minimum(X_cost[t], Y_cost[u])).sum()
			ans[size] = min(ans[size], cost)
			if t == 0:
				break
			t = (t - 1) & s
	for Ans in ans:
		print(Ans)
if sys.argv[-1] == 'ONLINE_JUDGE':
	import numba
	from numba.pycc import CC
	i8 = numba.int64
	cc = CC('my_module')
 
	def cc_export(f, signature):
		cc.export(f.__name__, signature)(f)
		return numba.njit(f)
 
	main = cc_export(main, (i8[:], ))
	cc.compile()
 
from my_module import main

resolve()

Submission status: Runtime Error

Solution code:
import os
import sys
import numpy as np

def solve(inp):
    n = inp[0]
    xxx = inp[1::3]
    yyy = inp[2::3]
    ppp = inp[3::3]
 
    ans = np.full(n + 1, 10 ** 18, dtype=np.int64)
 
    default_dist = np.zeros(n, dtype=np.int64)
    for i in range(n):
        default_dist[i] = min(abs(xxx[i]), abs(yyy[i]))
 
    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)
 
        i = 0
        cur = 0
        t = bit
        selected = np.zeros(k, dtype=np.int64)
        is_selected = np.zeros(n, dtype=np.int8)
        while t:
            if t & 1:
                selected[cur] = i
                is_selected[i] = 1
                cur += 1
            t >>= 1
            i += 1
 
        for bit2 in range(1 << k):
            cost = 0
            for i in range(n):
                if is_selected[i]:
                    continue
                town_dist = default_dist[i]
                t = bit2
                for j in range(k):
                    if t & 1:
                        town_dist = min(town_dist, abs(yyy[selected[j]] - yyy[i]))
                    else:
                        town_dist = min(town_dist, abs(xxx[selected[j]] - xxx[i]))
                    t >>= 1
                cost += town_dist * ppp[i]
            kk = len(selected)
            ans[kk] = min(ans[kk], cost)
 
    return ans

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
 
    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()
    
if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit
 
    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)
    
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))