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

main()

Solution (Python):
inf = 10**15


def main():
    import sys
    input = sys.stdin.readline

    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 = [[inf] * N for _ in range(1<<N)]
    dy = [[inf] * N for _ in range(1<<N)]
    for i in range(1 << N):
        Xline = [0]
        Yline = [0]
        for j in range(N):
            if i>>j&1:
                Xline.append(X[j])
                Yline.append(Y[j])
        for j in range(N):
            for x, y in zip(Xline, Yline):
                dx[i][j] = min(dx[i][j], abs(x - X[j]))
                dy[i][j] = min(dy[i][j], abs(y - Y[j]))

    ans = [inf] * (N+1)
    beki = [1<<j for j in range(N)]
    for i in range(3**(N-1)):
        M = i
        k = 0
        ix = iy = 0
        J = []
        for j in range(N-1):
            M, m = divmod(M, 3)
            if m == 0:
                J.append(j)
            elif m == 1:
                k += 1
                ix += beki[j]
            else:
                k += 1
                iy += beki[j]
        for x in range(3):
            kk = k
            ix_ = ix
            iy_ = iy
            if x == 0:
                J.append(N-1)
            elif x == 1:
                kk += 1
                ix_ += beki[N-1]
            else:
                kk += 1
                iy_ += beki[N-1]
            cost = 0
            for j in J:
                p = P[j]
                cost += min(dx[ix_][j], dy[iy_][j]) * p
            ans[kk] = min(ans[kk], cost)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()

Solution (Python):
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':
    
    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)))

Solution (Python):


import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

costs = [sys.maxsize] * N
for i, (x, y, c) in enumerate(XYP):
    costs[i] = c * min(abs(x), abs(y))

x_cost = [sys.maxsize] * ((1 << N) * N)
y_cost = [sys.maxsize] * ((1 << N) * N)

for bit in range(1 << N):
    for i, (xi, yi, _) in enumerate(XYP):
        x_cost[bit * N + i] = min(costs[i], x_cost[bit * N + i])
        y_cost[bit * N + i] = min(costs[i], y_cost[bit * N + i])
        if not (bit & (1 << i)):
            continue
        for k, (xk, yk, c) in enumerate(XYP):
            x_cost[bit * N + k] = min(x_cost[bit * N + k], abs(xi - xk) * c)
            y_cost[bit * N + k] = min(y_cost[bit * N + k], abs(yi - yk) * c)

ans = [sys.maxsize] * (N + 1)

for bit in range(1 << N):
    cnt = bin(bit).count('1')
    bit_ = bit
    while bit_ >= 0:
        bit_ &= bit
        cost = 0
        y_bit = bit - bit_
        for k in range(N):
            cost += min(x_cost[bit_ * N + k], y_cost[(y_bit) * N + k])
        ans[cnt] = min(ans[cnt], cost)

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

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

DX = [[0] * N for _ in range(1 << N)]
DY = [[0] * N for _ in range(1 << N)]

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

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

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

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


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

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

DX = [[0] * N for _ in range(1 << N)]
DY = [[0] * N for _ in range(1 << N)]

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

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

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

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


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

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

DX = [[0] * N for _ in range(1 << N)]
DY = [[0] * N for _ in range(1 << N)]

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

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

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

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


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

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

DX = [[0] * N for _ in range(1 << N)]
DY = [[0] * N for _ in range(1 << N)]

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

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

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

mm = (1 << N) - 1
for i in range(1 << N):
    m = i ^ mm
    j = m
    while 1:
        ans = 0
        for k in RA[i^j^mm]:
            ans += min(DX[i][k], DY[j][k])
        
        pc = PC[i] + PC[j]
        ANS[pc] = min(ANS[pc], ans)
        
        if not j:
            break
        j = m & (j - 1)


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

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

DX = [[0] * (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):
    PC[i] = PC[i^1] + 1 if i % 2 else PC[i//2]

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

mm = (1 << N) - 1
for i in range(1 << N):
    m = i ^ mm
    j = m
    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")

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

DX = []
DY = []

for i, x in enumerate(X):
    t = []
    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))
        t.append(d * P[i])
    DX.append(t)
for i, y in enumerate(Y):
    t = []
    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))
        t.append(d * P[i])
    DY.append(t)

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

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

DX = [[0] * (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

mm = (1 << N) - 1
RA = [[] for _ in range(1 << N)]
for i in range(1 << N):
    t = []
    for j in range(N):
        if i & (1 << j):
            t.append(j)
    RA[i^mm] = tuple(t)

for i in range(1 << N):
    m = i ^ mm
    j = m
    while 1:
        ans = 0
        for k in RA[i^j]:
            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")

Solution (Python):



n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13







costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))

OFFSET = n
x_dir = [INF] * ((1 << n) * OFFSET)
y_dir = [INF] * ((1 << n) * OFFSET)


for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[bit_state * OFFSET + i] = min(costs[i], x_dir[bit_state * OFFSET + i])
        y_dir[bit_state * OFFSET + i] = min(costs[i], y_dir[bit_state * OFFSET + i])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[bit_state * OFFSET + j] = min(x_dir[bit_state * OFFSET + j], c * abs(yi - yj))
            y_dir[bit_state * OFFSET + j] = min(y_dir[bit_state * OFFSET + j], c * abs(xi - xj))


ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        
        
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[x_bit * OFFSET + i], y_dir[y_bit * OFFSET + i])
        ans[cnt] = min(ans[cnt], tmp)
        
        x_bit -= 1

ans[-1] = 0
for res in ans:
    print(res)

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

DX = [[0] * (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")

Solution (Python):
import sys
import numpy as np

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

def main(XYP):
    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
    N = len(X)
    dp_X = np.empty((1 << N, N), np.int64)  
    dp_X[0] = np.abs(X) * P
    for n in range(N):
        B = 1 << n
        dp_X[B:2 * B] = np.minimum(dp_X[:B], np.abs(X - X[n]) * P)

    dp_Y = np.empty((1 << N, N), np.int64)  
    dp_Y[0] = np.abs(Y) * P
    for n in range(N):
        B = 1 << n
        dp_Y[B:2 * B] = np.minimum(dp_Y[:B], np.abs(Y - Y[n]) * P)

    popcount = np.zeros(1 << N, np.int64)
    for n in range(N):
        popcount[1 << n:1 << n + 1] = popcount[:1 << n] + 1

    INF = 10**18
    ans = np.full(N + 1, INF, np.int64)
    for s in range(1 << N):
        size = popcount[s]
        t = s
        while True:
            u = s ^ t
            cost = (np.minimum(dp_X[t], dp_Y[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)

    main = cc_export(main, (i8[:], ))
    cc.compile()

from my_module import main

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

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

Solution (Python):
import bisect

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
import numpy as np
import numba
from numba import njit
i8 = numba.int64

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

@njit((i8[:], ), cache=True)
def main(XYP):
    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
    N = len(X)
    dp_X = np.empty((1 << N, N), np.int64)  
    dp_X[0] = np.abs(X) * P
    for n in range(N):
        B = 1 << n
        dp_X[B:2 * B] = np.minimum(dp_X[:B], np.abs(X - X[n]) * P)

    dp_Y = np.empty((1 << N, N), np.int64)  
    dp_Y[0] = np.abs(Y) * P
    for n in range(N):
        B = 1 << n
        dp_Y[B:2 * B] = np.minimum(dp_Y[:B], np.abs(Y - Y[n]) * P)

    popcount = np.zeros(1 << N, np.int64)
    for n in range(N):
        popcount[1 << n:1 << n + 1] = popcount[:1 << n] + 1

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

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

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

Solution (Python):
import 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':
    
    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)))

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


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

INF = 10**18

def scores(Xs):
    L = len(Xs)
    dp = [[INF]*(L+1) for _ in range(L+1)]
    
    init = 0
    for x, p in Xs:
        init += abs(x)*p
    if L == 0:
        return [0]
    
    for ix, (x, p) in enumerate(Xs):
        dp[ix][0] = init
        score = 0
        for jx, (y, q) in enumerate(Xs):
            score += min(abs(y)*q, abs(x-y)*q)
        dp[ix][1] = score
    
    
    for k in range(1, L):
        for ix, (x, p) in enumerate(Xs):
            for iy in range(ix+1, L):
                y, q = Xs[iy]
                tmp = dp[ix][k]
                for iz in range(ix+1, L):
                    z, r = Xs[iz]
                    new = abs(z-y)
                    pre = min(abs(z), abs(z-x))
                    if new < pre:
                        tmp += (new - pre)*r
                dp[iy][k+1] = min(dp[iy][k+1], tmp)
    
    ret = [INF]*(L+1)
    for k in range(L+1):
        for j in range(L+1):
            ret[k] = min(dp[j][k], ret[k])

    return ret

ans = [INF]*(N+1)
for bit in range(1<<N):
    Xs = []
    Ys = []
    for i, (x, y, p) in enumerate(XYP):
        if (1<<i)&bit:
            Xs.append((x, p))
        else:
            Ys.append((y, p))

    Xs.sort()
    Ys.sort()
    dpx = scores(Xs)
    dpy = scores(Ys)
    for i, x in enumerate(dpx):
        for j, y in enumerate(dpy):
            ans[i+j] = min(ans[i+j], x+y)

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

Solution (Python):
from bisect import bisect_left

n = int(input())
xyp = [list(map(int, input().split())) for i in range(n)]
inf = 1<<63
tate = [[] for i in range(1<<n)]
yoko = [[] for i in range(1<<n)]
state_ind = [[] for i in range(1<<n)]
for state in range(1<<n):
    tmp_x = [0]
    tmp_y = [0]
    for i in range(n):
        if state & (1<<i):
            tmp_x.append(xyp[i][0])
            tmp_y.append(xyp[i][1])
        else:
            state_ind[state].append(i)
    tmp_x.sort()
    tmp_y.sort()
    x_score = [0]*n
    y_score = [0]*n
    nn = len(tmp_x)
    mm = len(tmp_y)
    for i, (x,y,p) in enumerate(xyp):
        j = bisect_left(tmp_x,x)
        if j == 0:
            x_m = tmp_x[0]-x
        elif j == nn:
            x_m = x-tmp_x[nn-1]
        else:
            x_m = min(x-tmp_x[j-1], tmp_x[j]-x)
        j = bisect_left(tmp_y,y)
        if j == 0:
            y_m = tmp_y[0]-y
        elif j == mm:
            y_m = y-tmp_y[mm-1]
        else:
            y_m = min(y-tmp_y[j-1], tmp_y[j]-y)
        x_score[i] = x_m * p
        y_score[i] = y_m * p
    tate[state] = x_score
    yoko[state] = y_score

ans = [inf]*(1<<n)
for state in range(1<<n):
    j = state
    while j>=0:
        j &= state
        i = state^j
        tmp1 = 0
        for k in state_ind[state]:
            if tate[i][k] < yoko[j][k]:
                tmp1 += tate[i][k]
            else:
                tmp1 += yoko[j][k]
            if tmp1 >= ans[state]:
                break
        if tmp1 < ans[state]:
            ans[state] = tmp1 
        j -= 1

cnt = [0]*(1<<n)
for i in range(1<<(n-1)):
    cnt[2*i] = cnt[i]
    cnt[2*i+1] = cnt[i]+1

ans_k = [inf]*(n+1)
for state in range(1<<n):
    k = cnt[state]
    if ans_k[k] > ans[state]:
        ans_k[k] = ans[state]
print(*ans_k, sep="\n")