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:
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())
    city = list(zip(*[iter(XYP)] * 3))

    dist_x = [[abs(c[0]) for c in city] for _ in range(1 << N)]
    dist_y = [[abs(c[1]) for c in city] 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, p) in enumerate(city):
                if dist_x[i][k] > abs(x - city[j][0]):
                    dist_x[i][k] = abs(x - city[j][0])
                if dist_y[i][k] > abs(y - city[j][1]):
                    dist_y[i][k] = abs(y - city[j][1])

    cost = [INF] * (N + 1)

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

        ans = INF
        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:
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)
    beki2 = [1<<j for j in range(N)]
    for i in range(3**N):
        M = i
        k = 0
        ix = iy = 0
        J = []
        for j in range(N):
            M, m = divmod(M, 3)
            if m == 0:
                J.append(j)
            elif m == 1:
                k += 1
                ix += beki2[j]
            else:
                k += 1
                iy += beki2[j]
        cost = 0
        for j in J:
            p = P[j]
            cost += min(dx[ix][j], dy[iy][j]) * p
        ans[k] = min(ans[k], cost)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()

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):
            j &= i
            cost = 0
            for k in range(n):
                if not (i>>k)&1:
                    cost += min(xcost[j, k], ycost[i-j, k])
            ans[cnt] = min(ans[cnt], cost)
    for x in ans:
        print(x)

             
            
        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

def solve(n, XYP):
    def convert(x, n=2, k=0):
        A = deque()
        while x:
            x, r = divmod(x, n)
            A.appendleft(r)
        return ''.join(map(str, A)).zfill(k)
    
    def preprocess(n, XYP):
        d_x = {}
        d_y = {}
        for i in range(2**n):
            X, Y = [0], [0]
            for j, (x, y, p) in enumerate(XYP):
                if (i>>j) & 1:
                    X.append(x)
                    Y.append(y)
            Z, W = [], []
            for x, y, p in XYP:
                Z.append(min(abs(x-x_) for x_ in X) * p)
                W.append(min(abs(y-y_) for y_ in Y) * p) 
            d_x[str(X)] = Z
            d_y[str(Y)] = W
        return d_x, d_y
    d_x, d_y = preprocess(n, XYP)
    
    A = defaultdict(lambda:1<<64)
    for i in range(3**n):
        S = list(map(int, convert(i, 3, n)))
        c = 0
        X, Y = [0], [0]
        for s, (x, y, p) in zip(S, XYP):
            if s == 1:
                X.append(x)
                c += 1
            elif s == 2:
                Y.append(y)
                c += 1
        s = sum(min(d_x[str(X)][j], d_y[str(Y)][j]) for j in range(n))
        if A[c] > s:
            A[c] = s
    for i in range(n+1):
        print(A[i])

n, *XYP = map(int, open(0).read().split())
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))
solve(n, XYP)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9
inf = 10**9


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

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

    dx = [[inf] * (1<<N) for _ in range(N)]
    dy = [[inf] * (1<<N) for _ in range(N)]
    for i in range(1 << N):
        L = []
        Xline = [0]
        Yline = [0]
        for j in range(N):
            if i>>j&1:
                Xline.append(XYP[j][0])
                Yline.append(XYP[j][1])
        for j in range(N):
            for x, y in zip(Xline, Yline):
                dx[j][i] = min(dx[j][i], abs(x - XYP[j][0]))
                dy[j][i] = min(dy[j][i], abs(y - XYP[j][1]))

    ans = [float("inf")] * (N+1)
    for i in range(3**N):
        M = i
        L = []
        k = 0
        ix = iy = 0
        for j in range(N):
            if M%3 == 1:
                k += 1
                ix += 1 << j
            elif M%3 == 2:
                k += 1
                iy += 1 << j
            M //= 3
        cost = 0
        for j in range(N):
            p = XYP[j][2]
            cost += min(dx[j][ix], dy[j][iy]) * p
        ans[k] = min(ans[k], cost)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def Base_10_to_n(X, n, m):
    X_dumy = X
    out = ''
    while X_dumy > 0:
        out = str(X_dumy % n) + out
        X_dumy = int(X_dumy / n)
    return "0" * (m - len(out)) + out
    
n = int(input())
date = [list(map(int, input().split())) for i in range(n)]
distance0 = [float("INF")] * n
ans = [float("INF")] * (n + 1)
s = 0
for i in range(n):
    if distance0[i] > min(abs(date[i][0]), abs(date[i][1])):
        distance0[i] = min(abs(date[i][0]), abs(date[i][1]))
        s += distance0[i] * date[i][2]
ans[0] = s


for i in range(3 ** n):
    tri = Base_10_to_n(i, 3, n)
    cnt = 0
    s = ans[0]
    dis = distance0[:]
    for j in range(n):
        if tri[j] == "1":
            for k in range(n):
                if dis[k] > abs(date[j][0] - date[k][0]):
                    s -= (dis[k] - abs(date[j][0] - date[k][0])) * date[k][2]
                    dis[k] = abs(date[j][0] - date[k][0])
            cnt += 1
        elif tri[j] == "2":
            for k in range(n):
                if dis[k] > abs(date[j][1] - date[k][1]):
                    s -= (dis[k] - abs(date[j][1] - date[k][1])) * date[k][2]
                    dis[k] = abs(date[j][1] - date[k][1])
            cnt += 1
    ans[cnt] = min(ans[cnt], s)

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
village = []
for i in range(N):
    Xi, Yi, Pi = map(int, input().split())
    village.append((Xi, Yi, Pi))    

def score(streets):
    s = 0
    for v in village:
        min_dist = min(abs(v[0]), abs(v[1]))
        for street in streets:
            if abs(v[0] - street[0]) < min_dist:
                min_dist = abs(v[0] - street[0])
            if abs(v[1] - street[1]) < min_dist:
                min_dist = abs(v[1] - street[1])
        # print(v, min_dist)
        s += v[2] * min_dist
    return s

candidate = set()
for v in village:
    candidate.add((v[0], 0))
    candidate.add((0, v[1]))

m = score([(0, 0)])
prev_score = -1
for k in range(N + 1):
    if prev_score == 0:
        print(0)
        continue
    min_score = m
    min_streets = []
    for streets in itertools.combinations(candidate, k):
        # score
        s = score(streets)
        # print(streets, s)
        if s < min_score:
            min_streets = streets
            min_score = s
    prev_score = min_score
    print(min_score)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

def solve(n, XYP):
    def convert(x, n=2, k=0):
        A = deque()
        while x:
            x, r = divmod(x, n)
            A.appendleft(r)
        return ''.join(map(str, A)).zfill(k)
    
    def preprocess(n, XYP):
        dx = {}
        dy = {}
        for i in range(2**n):
            X, Y = [0], [0]
            for j, (x, y, p) in enumerate(XYP):
                if (i>>j) & 1:
                    X.append(x)
                    Y.append(y)
            Z, W = [], []
            for x, y, p in XYP:
                Z.append(min(abs(x-x_) for x_ in X) * p)
                W.append(min(abs(y-y_) for y_ in Y) * p) 
            dx[str(X)] = Z
            dy[str(Y)] = W
        return dx, dy
    dx, dy = preprocess(n, XYP)
    
    A = defaultdict(lambda: float('inf'))
    for i in range(3**n):
        S = convert(i, 3, n)
        c = S.count('1') + S.count('2')
        X, Y = [0], [0]
        for j, (x, y, p) in enumerate(XYP):
            if S[j] == '1':
                X.append(x)
            elif S[j] == '2':
                Y.append(y)
        s = sum(min(dx[str(X)][i], dy[str(Y)][i]) for i in range(n))
        if A[c] > s:
            A[c] = s
    for i in range(n+1):
        print(A[i])

n, *XYP = map(int, open(0).read().split())
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))
solve(n, XYP)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

def convert(x, n=2, k=0):
    A = deque()
    while x:
        x, r = divmod(x, n)
        A.appendleft(r)
    return ''.join(map(str, A)).zfill(k)

n, *XYP = map(int, open(0).read().split())
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))

def preprocess(n, XYP):
    dx = {}
    dy = {}
    for i in range(2**n):
        X, Y = [0], [0]
        for j, (x, y, p) in enumerate(XYP):
            if (i>>j) & 1:
                X.append(x)
                Y.append(y)
        Z, W = [], []
        for x, y, p in XYP:
            Z.append(min(abs(x-x_) for x_ in X) * p)
            W.append(min(abs(y-y_) for y_ in Y) * p) 
        dx[str(X)] = Z
        dy[str(Y)] = W
    return dx, dy

def process(n, XYP, dx, dy):
    A = defaultdict(lambda: float('inf'))
    for i in range(3**n):
        S = convert(i, 3, n)
        c = S.count('1') + S.count('2')
        X, Y = [0], [0]
        for j, (x, y, p) in enumerate(XYP):
            if S[j] == '1':
                X.append(x)
            elif S[j] == '2':
                Y.append(y)
        s = sum(min(dx[str(X)][i], dy[str(Y)][i]) for i in range(n))
        if A[c] > s:
            A[c] = s
    for i in range(n+1):
        print(A[i])

dx, dy = preprocess(n, XYP)
process(n, XYP, dx, dy)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

def convert(x, n=2, k=0):
    A = deque()
    while x:
        x, r = divmod(x, n)
        A.appendleft(r)
    return ''.join(map(str, A)).zfill(k)

n, *XYP = map(int, open(0).read().split())
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))

def preprocess(n, XYP):
    dx = {}
    dy = {}
    for i in range(2**n):
        X, Y = [0], [0]
        for j, (x, y, p) in enumerate(XYP):
            if (i>>j) & 1:
                X.append(x)
                Y.append(y)
        xk, yk = str(X), str(Y)
        Z, W = [], []
        for x, y, p in XYP:
            Z.append(min(abs(x-x_) for x_ in X) * p)
            W.append(min(abs(y-y_) for y_ in Y) * p)
        dx[xk] = Z
        dy[yk] = W
    return dx, dy

def process(n, XYP, dx, dy):
    A = defaultdict(lambda: float('inf'))
    for i in range(3**n):
        S = convert(i, 3, n)
        c = S.count('1') + S.count('2')
        X, Y = [0], [0]
        for j, (x, y, p) in enumerate(XYP):
            if S[j] == '1':
                X.append(x)
            elif S[j] == '2':
                Y.append(y)
        xk, yk = str(X), str(Y)
        s = sum(min(dx[xk][i], dy[yk][i]) for i in range(n))
        if A[c] > s:
            A[c] = s
    for i in range(n+1):
        print(A[i])

dx, dy = preprocess(n, XYP)
process(n, XYP, dx, dy)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    def I():
        return int(sys.stdin.readline().rstrip())

    def MI():
        return map(int, sys.stdin.readline().rstrip().split())

    N = I()
    X, Y, P = [], [], []
    for i in range(N):
        x, y, p = MI()
        X.append(x)
        Y.append(y)
        P.append(p)

    Z, W = [[] for _ in range(1 << N)], [[] for _ in range(1 << N)]
    for i in range(1 << N):
        A = []
        for j in range(N):
            if (i >> j) & 1:
                A.append(j)
        B, C = [10 ** 18] * N, [10 ** 18] * N
        for j in range(N):
            b = abs(X[j])
            c = abs(Y[j])
            for k in A:
                b = min(b, abs(X[j] - X[k]))
                c = min(c, abs(Y[j] - Y[k]))
            b *= P[j]
            B[j] = b
            c *= P[j]
            C[j] = c
        Z[i] = B
        W[i] = C

    ANS = [10 ** 18] * (N + 1)

    from itertools import product

    for a in product([0, 1, 2], repeat=N):
        b, c = 0, 0
        d = 0  # 0 の個数
        for i in range(N):
            if a[i] == 0:  # Xi,Yi からは選ばない
                d += 1
            elif a[i] == 1:  # Xi を選ぶ
                b += 1 << i
            else:  # Yi を選ぶ
                c += 1 << i
        e = 0
        for i in range(N):
            e += min(Z[b][i], W[c][i])
        d = N - d
        ANS[d] = min(ANS[d], e)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N = I()
X,Y,P = [],[],[]
for i in range(N):
    x,y,p = MI()
    X.append(x)
    Y.append(y)
    P.append(p)

Z,W = [[] for _ in range(1 << N)],[[] for _ in range(1 << N)]
for i in range(1 << N):
    A = []
    for j in range(N):
        if (i >> j) & 1:
            A.append(j)
    B,C = [10**18]*N,[10**18]*N
    for j in range(N):
        b = abs(X[j])
        c = abs(Y[j])
        for k in A:
            b = min(b,abs(X[j]-X[k]))
            c = min(c,abs(Y[j]-Y[k]))
        b *= P[j]
        B[j] = b
        c *= P[j]
        C[j] = c
    Z[i] = B
    W[i] = C

ANS = [10**18]*(N+1)

from itertools import product

for a in product([0,1,2],repeat=N):
    b,c = 0,0
    d = 0  # 0 の個数
    for i in range(N):
        if a[i] == 0:  # Xi,Yi からは選ばない
            d += 1
        elif a[i] == 1:  # Xi を選ぶ
            b += 1 << i
        else:  # Yi を選ぶ
            c += 1 << i
    e = 0
    for i in range(N):
        e += min(Z[b][i],W[c][i])
    d = N-d
    ANS[d] = min(ANS[d],e)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

n = int(input())
x = [0]*n
y = [0]*n
p = [0]*n
for i in range(n): x[i],y[i],p[i] = map(int,input().split())

distx = []
disty = []
for i in range(1<<n):
    dx = [abs(j) for j in x]
    dy = [abs(j) for j in y]
    flag = [False]*n
    for j in range(n):
        if i >> j & 1: flag[j] = True
    for j in range(n):
        for k in range(n):
            if flag[k]:
                dx[j] = min(dx[j],abs(x[j]-x[k]))
                dy[j] = min(dy[j],abs(y[j]-y[k]))
    distx.append(dx)
    disty.append(dy) 

INF = float("INF")
ans = [INF]*(n+1)
def f(s):
    if len(s) == n:
        tar = n-s.count("n")
        ix = 0
        iy = 0
        d = 1
        for c in s:
            if c == "x": ix += d
            elif c == "y": iy += d
            d *= 2
        res = 0
        for i in range(n): res += min(distx[ix][i],disty[iy][i])*p[i]
        ans[tar] = min(ans[tar],res)
        return
    for c in ("x","y","n"): f(s+c)
f("")
for i in range(n+1): print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def convert(x, n=2, k=0):
    A = []
    while x:
        x, r = divmod(x, n)
        A.append(r)
    return ''.join(map(str, reversed(A))).zfill(k)

n, *XYP = map(int, open(0).read().split())
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))
A = defaultdict(lambda: float('inf'))
dx = {}
dy = {}
for i in range(2**n):
    X, Y = [0], [0]
    for j, (x, y, p) in enumerate(XYP):
        if (i>>j) & 1:
            X.append(x)
            Y.append(y)
    xk, yk = str(X), str(Y)
    Z, W = [], []
    for x, y, p in XYP:
        Z.append(min(abs(x-x_) for x_ in X) * p)
        W.append(min(abs(y-y_) for y_ in Y) * p)
    dx[xk] = Z
    dy[yk] = W

for i in range(3**n):
    S = convert(i, 3, n)
    c = S.count('1') + S.count('2')
    X, Y = [0], [0]
    for j, (x, y, p) in enumerate(XYP):
        if S[j] == '1':
            X.append(x)
        elif S[j] == '2':
            Y.append(y)
    xk, yk = str(X), str(Y)
    s = sum(min(dx[xk][i], dy[yk][i]) for i in range(n))
    if A[c] > s:
        A[c] = s
for i in range(n+1):
    print(A[i])

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()



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

idle_max=10**18

def hogeX(Xlst):
    lst=[]
    for x,y,p in XYP:
        c=idle_max
        for X in Xlst:
            c=min(round(abs(X-x))*p,c)
        lst.append(c)
    return(lst)
def hogeY(Ylst):
    lst=[]
    for x,y,p in XYP:
        c=idle_max
        for Y in Ylst:
            c=min(round(abs(Y-y))*p,c)
        lst.append(c)
    return(lst)

def main(Alst,Blst):
    sumc=0
    for i in range(len(Alst)):
        sumc+=min(Alst[i],Blst[i])
    return (sumc)

def premain(Xlst,Ylst):
    sumc=0
    for x,y,p in XYP:
        c=idle_max
        for X in Xlst:
            c=min(round(abs(X-x))*p,c)
        for Y in Ylst:
            c=min(round(abs(Y-y))*p,c)
        sumc+=c
    return (sumc)

scorelst=[idle_max for i in range(N+1)]
XlstLst=[[] for i in range(N+1)]
YlstLst=[[] for i in range(N+1)]
for bit in product(range(2), repeat=N):
    Xlst=[0]
    Ylst=[0]
    for n in range(N):
        if bit[n]:
            x,y,p=XYP[n]
            Xlst.append(x)
            Ylst.append(y)
    XlstLst[sum(bit)].append(hogeX(Xlst))
    YlstLst[sum(bit)].append(hogeY(Ylst))

for K in range(N+1):
    for x in range(K+1):
        for Xlst in XlstLst[x]:
            for Ylst in YlstLst[K-x]:
                #print(K)
                scorelst[K]=min(scorelst[K],main(Xlst,Ylst))
scorelst[0]=premain([0],[0])
for score in scorelst:
    print(score)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N = I()
X,Y,P = [],[],[]
for i in range(N):
    x,y,p = MI()
    X.append(x)
    Y.append(y)
    P.append(p)

Z,W = [],[]
for i in range(2**N):
    A = []
    for j in range(N):
        if (i >> j) & 1:
            A.append(j)
    B,C = [],[]
    for j in range(N):
        b = abs(X[j])
        c = abs(Y[j])
        for k in A:
            b = min(b,abs(X[j]-X[k]))
            c = min(c,abs(Y[j]-Y[k]))
        b *= P[j]
        B.append(b)
        c *= P[j]
        C.append(c)
    Z.append(B)
    W.append(C)

ANS = [10**18]*(N+1)

from itertools import product

for a in product([0,1,2],repeat=N):
    b,c = 0,0
    d = 0  # 0 の個数
    for i in range(N):
        if a[i] == 0:  # Xi,Yi からは選ばない
            d += 1
        elif a[i] == 1:  # Xi を選ぶ
            b += 1 << i
        else:  # Yi を選ぶ
            c += 1 << i
    e = 0
    for i in range(N):
        e += min(Z[b][i],W[c][i])
    d = N-d
    ANS[d] = min(ANS[d],e)

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

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3

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

x_cost = [0] * ((1 << N) * N)
y_cost = [0] * ((1 << N) * N)

for bit in range(1 << N):
    for i, (xi, yi, _) in enumerate(XYP):
        x_cost[bit * N + i] = abs(xi)
        y_cost[bit * N + i] = abs(yi)

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

ans = [sys.maxsize for _ in range(N + 1)]

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def convert(x, n=2, k=0):
    A = []
    while x:
        x, r = divmod(x, n)
        A.append(r)
    return ''.join(map(str, reversed(A))).zfill(k)

n, *XYP = map(int, open(0).read().split())
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))
A = defaultdict(lambda: float('inf'))
dx = {}
dy = {}
for i in range(2**n):
    X = [0]
    Y = [0]
    for j, (x, y, p) in enumerate(XYP):
        if (i>>j) & 1:
            X.append(x)
            Y.append(y)
    xk = str(X)
    yk = str(Y)
    Z = []
    W = []
    for x, y, p in XYP:
        Z.append(min(abs(x-x_) for x_ in X) * p)
        W.append(min(abs(y-y_) for y_ in Y) * p)
    dx[xk] = Z        
    dy[yk] = W

for i in range(3**n):
    X = [0]
    Y = [0]
    S = convert(i, 3, n)
    c = S.count('1') + S.count('2')
    for j, (x, y, p) in enumerate(XYP):
        if S[j] == '1':
            X.append(x)
        elif S[j] == '2':
            Y.append(y)
    xk = str(X)
    yk = str(Y)
    s = 0
    for i in range(n):
        s += min(dx[xk][i], dy[yk][i])
    if A[c] > s:
        A[c] = s
for i in range(n+1):
    print(A[i])

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3

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

x_cost = [[0 for _ in range(N)] for _ in range(1 << N)]
y_cost = [[0 for _ in range(N)] for _ in range(1 << N)]

for bit in range(1 << N):
    for i in range(N):
        x_cost[bit][i] = abs(XYP[i][0])
        y_cost[bit][i] = abs(XYP[i][1])

        for k in range(N):
            if bit & (1 << k):
                x_cost[bit][i] = min(x_cost[bit][i], abs(XYP[i][0] - XYP[k][0]))
                y_cost[bit][i] = min(y_cost[bit][i], abs(XYP[i][1] - XYP[k][1]))

ans = [sys.maxsize for _ in range(N + 1)]

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

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()



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

idle_max=10**18

def main(Xlst,Ylst):
    sumc=0
    for x,y,p in XYP:
        c=idle_max
        for X in Xlst:
            c=min(round(abs(X-x))*p,c)
        for Y in Ylst:
            c=min(round(abs(Y-y))*p,c)
        sumc+=c
    return (sumc)

scorelst=[idle_max for i in range(N+1)]
XlstLst=[[] for i in range(N+1)]
YlstLst=[[] for i in range(N+1)]
for bit in product(range(2), repeat=N):
    Xlst=[0]
    Ylst=[0]
    for n in range(N):
        if bit[n]:
            x,y,p=XYP[n]
            Xlst.append(x)
            Ylst.append(y)
    XlstLst[sum(bit)].append(Xlst)
    YlstLst[sum(bit)].append(Ylst)

for K in range(N+1):
    for x in range(K+1):
        for Xlst in XlstLst[x]:
            for Ylst in YlstLst[K-x]:
                #print(K)
                scorelst[K]=min(scorelst[K],main(Xlst,Ylst))
scorelst[0]=main([0],[0])
for score in scorelst:
    print(score)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def convert(x, n=2, k=0):
    A = []
    while x:
        x, r = divmod(x, n)
        A.append(r)
    return ''.join(map(str, reversed(A))).zfill(k)

n, *XYP = map(int, open(0).read().split())
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))
A = defaultdict(lambda: float('inf'))
dx = {}
dy = {}
for i in range(2**n):
    X = [0]
    Y = [0]
    for j, (x, y, p) in enumerate(XYP):
        if (i>>j) & 1:
            X.append(x)
            Y.append(y)
    xk = str(sorted(set(X)))
    yk = str(sorted(set(Y)))
    Z = []
    W = []
    for x, y, p in XYP:
        Z.append(min(abs(x-x_) for x_ in X) * p)
        W.append(min(abs(y-y_) for y_ in Y) * p)
    dx[xk] = Z        
    dy[yk] = W

for i in range(3**n):
    L = [0, 0]
    S = convert(i, 3, n)
    c = S.count('1') + S.count('2')
    for j, (x, y, p) in enumerate(XYP):
        if S[j] == '1':
            L += [x, 0]
        elif S[j] == '2':
            L += [0, y]
    s = 0
    xk = str(sorted(set(L[::2])))
    yk = str(sorted(set(L[1::2])))
    for i in range(n):
        s += min(dx[xk][i], dy[yk][i])
    if A[c] > s:
        A[c] = s
for i in range(n+1):
    print(A[i])