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:
from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: M -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cost = 0
    for x, y in zip(costX[stateX], costY[stateY]):
        cost += min(x, y)

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range((1 << N) + 100)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state + 100][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: M -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cost = 0
    for x, y in zip(costX[stateX + 100], costY[stateY + 100]):
        cost += min(x, y)

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << (N + 1))]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state << 1][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        if s == 0: M -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1
        stateX <<= 1
        stateY <<= 1

    cx = costX[stateX]
    cy = costY[stateY]

    cost = 0
    for x, y in zip(costX[stateX], costY[stateY]):
        cost += min(x, y)

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

MEM = [0] * (10**6)

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: M -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cx = costX[stateX]
    cy = costY[stateY]

    cost = 0
    for x, y in zip(costX[stateX], costY[stateY]):
        cost += min(x, y)

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

MEM = [0] * (10**6)

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

def makeState(state, sign):
    ret = 0
    for s in state:
        ret <<= 1
        if s == sign:
            ret |= 1
    return ret

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: M -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cx = costX[stateX]
    cy = costY[stateY]

    cost = 0
    for i in range(N):
        cost += min(cx[i], cy[i])

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    def makeState(state, sign):
        ret = 0
        for s in state:
            ret <<= 1
            if s == sign:
                ret |= 1
        return ret

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx = costX[stateX]
        cy = costY[stateY]

        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])

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

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

sol()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

def makeState(state, sign):
    ret = 0
    for s in state:
        ret <<= 1
        if s == sign:
            ret |= 1
    return ret

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: M -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cx = costX[stateX]
    cy = costY[stateY]

    cost = 0
    for i in range(N):
        cost += min(cx[i], cy[i])

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

def makeState(state, sign):
    ret = 0
    for s in state:
        ret <<= 1
        if s == sign:
            ret |= 1
    return ret

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: M -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cx = costX[stateX]
    cy = costY[stateY]

    cost = sum(min(x, y) for x, y in zip(cx, cy))

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

def makeState(state, sign):
    ret = 0
    for s in state:
        ret <<= 1
        if s == sign:
            ret |= 1
    return ret

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    cx = costX[makeState(state, 1)]
    cy = costY[makeState(state, 2)]

    cost = sum(min(x, y) for x, y in zip(cx, cy))

    M = N - state.count(0)
    if ans[M] > cost:
        ans[M] = cost

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    def makeState(state, sign):
        ret = 0
        for s in state[::-1]:
            ret <<= 1
            if s == sign:
                ret |= 1
        return ret

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = makeState(state, 1)
        stateY = makeState(state, 2)

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

        M = N - state.count(0)
        if ans[M] > cost:
            ans[M] = cost

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

sol()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    def makeState(state, sign):
        ret = 0
        for s in state[::-1]:
            ret <<= 1
            if s == sign:
                ret |= 1
        return ret

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

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

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

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

sol()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

def makeState(state, sign):
    ret = 0
    for s in state[::-1]:
        ret <<= 1
        if s == sign:
            ret |= 1
    return ret

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

def makeState(state, sign):
    ret = 0
    for s in state[::-1]:
        ret <<= 1
        if s == sign:
            ret |= 1
    return ret

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = makeState(state, 1)
    stateY = makeState(state, 2)

    cost = 0
    for i, (x, y, p) in enumerate(XYP):
        cost += min(costX[stateX][i], costY[stateY][i])

    M = N - state.count(0)
    if ans[M] > cost:
        ans[M] = cost

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

def makeState(state, sign):
    ret = 0
    for s in state[::-1]:
        ret <<= 1
        if s == sign:
            ret |= 1
    return ret

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    useX = set([x for i, x in enumerate(X) if state[i] == 1])
    useY = set([y for i, y in enumerate(Y) if state[i] == 2])

    stateX = makeState(state, 1)
    stateY = makeState(state, 2)

    cost = 0
    for i, (x, y, p) in enumerate(XYP):
        if x in useX or y in useY:
            continue
        cost += min(costX[stateX][i], costY[stateY][i])

    M = len(useX) + len(useY)
    if ans[M] > cost:
        ans[M] = cost

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

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n = int(ipt())
    xs = []
    ys = []
    ps = []
    for i in range(n):
        x,y,p = map(int,ipt().split())
        xs.append(x)
        ys.append(y)
        ps.append(p)
    mix = [abs(i) for i in xs]
    miy = [abs(i) for i in ys]
    mi2x = []
    mi2y = []
    for i in range(2**n):
        mi = mix*1
        for j,xj in enumerate(xs):
            if (i>>j)&1:
                for k,xk in enumerate(xs):
                    ax = abs(xj-xk)
                    if mi[k] > ax:
                        mi[k] = ax
        mi = [mi[i]*ps[i] for i in range(n)]
        mi2x.append(mi)
    for i in range(2**n):
        mi = miy*1
        for j,yj in enumerate(ys):
            if (i>>j)&1:
                for k,yk in enumerate(ys):
                    ay = abs(yj-yk)
                    if mi[k] > ay:
                        mi[k] = ay
        mi = [mi[i]*ps[i] for i in range(n)]
        mi2y.append(mi)

    mi = [10**18]*(n+1)
    for i in range(3**n):
        xi = 0
        yi = 0
        ii = i
        t = n
        for j in range(n):
            if ii%3 == 1:
                xi += 2**j
            elif ii%3 == 2:
                yi += 2**j
            else:
                t -= 1
            ii //= 3
        nm = 0
        for xii,yii in zip(mi2x[xi],mi2y[yi]):
            if xii > yii:
                nm += yii
            else:
                nm += xii
        if mi[t] > nm:
            mi[t] = nm

    for i in mi:
        print(i)

    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n = int(ipt())
    xs = []
    ys = []
    ps = []
    for i in range(n):
        x,y,p = map(int,ipt().split())
        xs.append(x)
        ys.append(y)
        ps.append(p)
    mix = [abs(i) for i in xs]
    miy = [abs(i) for i in ys]
    mi2x = []
    mi2y = []
    for i in range(2**n):
        mi = mix*1
        for j,xj in enumerate(xs):
            if (i>>j)&1:
                for k,xk in enumerate(xs):
                    ax = abs(xj-xk)
                    if mi[k] > ax:
                        mi[k] = ax
        mi = [mi[i]*ps[i] for i in range(n)]
        mi2x.append(mi)
    for i in range(2**n):
        mi = miy*1
        for j,yj in enumerate(ys):
            if (i>>j)&1:
                for k,yk in enumerate(ys):
                    ay = abs(yj-yk)
                    if mi[k] > ay:
                        mi[k] = ay
        mi = [mi[i]*ps[i] for i in range(n)]
        mi2y.append(mi)

    mi = [10**18]*(n+1)
    for i in range(3**n):
        xi = 0
        yi = 0
        ii = i
        t = n
        for j in range(n):
            if ii%3 == 1:
                xi += 2**j
            elif ii%3 == 2:
                yi += 2**j
            else:
                t -= 1
            ii //= 3
        xc = mi2x[xi]
        yc = mi2y[yi]
        nm = 0
        for xii,yii in zip(xc,yc):
            if xii > yii:
                nm += yii
            else:
                nm += xii
        if mi[t] > nm:
            mi[t] = nm

    for i in mi:
        print(i)

    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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**18+10

    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)
    for pattern in product(range(3),repeat=N):
        pattern_v = 0
        pattern_h = 0
        key = N
        for p in pattern:
            pattern_v *= 2
            pattern_h *= 2
            if p == 1:
                pattern_v += 1
            elif p == 2:
                pattern_h += 1
            else:
                key -= 1
        sum_diff = 0
        for i in range(N):
            sum_diff += min(v[pattern_v][i],h[pattern_h][i])

        ans[key] = min(ans[key], sum_diff)
    print('\n'.join(map(str,ans)))





            



    

    



    
main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

#準備：S_の外延表記sを求める
def settify(S):
  s = []
  i = 0
  while S > 0:
    if (S & 1):  
      s.append(i)
    S = S >> 1
    i += 1
  return s

Sets = []
for S_ in range(2**N):#MLEの可能性あり
  Sets.append(settify(S_))
  
#前処理：集合に対して最適な路線を一つ選ぶO(N^2*2^N)
B = [0 for _ in range(2**N)]
for S_ in range(2**N):
  if S_ == 0:
    ans = 0
    continue
  ans = 10 ** 20
  s = Sets[S_]
  for k in s:
    #南北方向の路線の場合
    sm1 = 0
    #東西方向の路線の場合
    sm2 = 0
    for l in s:
      sm1 += abs(A[k][0] - A[l][0]) * A[l][2]
      sm2 += abs(A[k][1] - A[l][1]) * A[l][2]
    ans = min(ans, sm1, sm2)
    #print(S_, s, ans, sm1, sm2) 
  B[S_] = ans
  
#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
  for i in Sets[S_]:
  #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): 
  """
  for i in Sets[S_]:
    C[S_] += abs(A[i][1])*A[i][2]
    #S = S >> 1
    #i += 1
  
#東西大通り
for S_ in range(2**N):
  if S_ == 0:
    continue
  s = Sets[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):
    """
    for i in Sets[T_]:
      L += 2**s[i]
      #T = T >> 1
      #i += 1
    DP[S_][1] = min(DP[S_][1], DP[S_-L][0] + C[L])

#DP[*][2~]を実行
for k in range(N): #DP[*][k+2]
  for S_ in range(2**N):
    if S_ == 0: continue
    #S = S_
    s = Sets[S_] 
    #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):
      """
      for i in Sets[T_]:
        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:
N = int(input())
city = []
for i in range(N):
  x,y,p = map(int,input().split())
  city.append((x,y,p))

xx = [ [ abs(city[j][0]) for j in range(N) ] for i in range(2<<N) ]
yy = [ [ abs(city[j][1]) for j in range(N) ] for i in range(2<<N) ]

for i in range(2<<N):
  X = [0]
  rest = []
  for j in range(N):
    if i>>j&1:
      X.append(city[j][0])
      xx[i][j] = 0
    else:
      rest.append(j)

  for j in rest:
    res = 10**15
    for k in X:
      res = min(res, abs(city[j][0]-k))
    xx[i][j] = res

for i in range(2<<N):
  Y = [0]
  rest = []
  for j in range(N):
    if i>>j&1:
      Y.append(city[j][1])
      yy[i][j] = 0
    else:
      rest.append(j)

  for j in rest:
    res = 10**15
    for k in Y:
      res = min(res, abs(city[j][1]-k))
    yy[i][j] = res


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

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

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