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())
U=product(["A","B","O"],repeat=N)
inf=float("inf")

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

T=[inf]*(N+1)
for i in range(N):
    T[-1]+=min(X)

for K in U:
    E={0}
    F={0}

    for i in range(N):
        if K[i]=="A":
            E.add(X[i])
        elif K[i]=="B":
            F.add(Y[i])

    C=0
    for i in range(N):
        A=min(E,key=lambda x:abs(x-X[i]))
        B=min(F,key=lambda y:abs(y-Y[i]))
        C+=min(abs(A-X[i]),abs(B-Y[i]))*P[i]

    M=len(E)+len(F)-2
    T[M]=min(T[M],C)

print("\n".join(map(str,T)))

Submission status: Time Limit Exceeded

Solution code:
#E
N=int(input())
XYP=[None]*N
for i in range(N):
    XYP[i] = list(map(int,input().split()))
import itertools
for k in range(0,N+1):
    ans=10**20
    for q in itertools.combinations(range(N), k):
        #print(q)
        for j in range(2**len(q)):
            bi = bin(j)[2:].zfill(len(q))
            r = [q[i] for i in range(len(q)) if bi[i]=="1"]
            #print(r,"r")
            X_trains = [XYP[i][0] for i in q if i in r]+[0]
            Y_trains = [XYP[i][1] for i in q if i not in r]+[0]
            cost = sum( XYP[k][2]*min([ abs(XYP[k][0]-x) for x in X_trains]+
                       [abs(XYP[k][1]-y) for y in Y_trains] ) for k in range(N) )
            ans=min(ans,cost)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools


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


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


x_dir = [[INF] * n for i in range(1 << n)]
y_dir = [[INF] * n for i in range(1 << n)]

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


ans = [INF] * (n + 1)

for bit_state in range(1 << n):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[x_bit][i], y_dir[y_bit][i])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

for res in ans:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
cities = []
S = 0
candx = []
candy = []
for _ in range(N):
    city = [int(i) for i in input().split()]
    candx.append(city[0])
    candy.append(city[1])
    cities.append(city)
    S += city[2]*min(abs(city[0]),abs(city[1]))
print(S)
for i in range(1,N):
    a = 0
    for j in range(i+1):
        for x in itertools.combinations(candx,j):
            z = 0
            for y in itertools.combinations(candy,i-j):
                draft = 0
                x = list(x)
                y = list(y)
                for city in cities:
                    dx = float("inf")
                    dy = float("inf")
                    if x:
                        dx = min([abs(city[0]-k) for k in x])
                    if y:
                        dy = min([abs(city[1]-k) for k in y])
                    draft += city[2]*(min(abs(city[0]),abs(city[1])) - min(abs(city[0]),abs(city[1]),dx,dy))
                a = max(a,draft)
                if S == a:
                    z = 1
                    break
            if z:
                break
    print(S-a)
    if S == a:
        for _ in range(N-i-1):
            print(0)
        break
print(0)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
X = [0]*N
Y = [0]*N
P = [0]*N
ans = [0]*(N+1)
for i in range(N):
  X[i] , Y[i] , P[i] = map(int,input().split()) 
S0 = max([max(X),max(Y)])*sum(P)  
def S(X,Y,P,LX,LY):
  s = 0
  nx = len(LX)
  ny = len(LY)
  for i in range(N):
    tempX = min([abs(X[i] - j) for j in LX])
    tempY = min([abs(Y[i] - j) for j in LY])
    d = min([tempX , tempY])
    s += d*P[i]
  return(s)  
for i in range(N+1):
  if S0 == 0:
    break
  for j in range(i):
    for k in range(i - j):
      for pairx in itertools.combinations(X,j):
        for pairy in itertools.combinations(Y,k):
          LX = list(pairx)
          LY = list(pairy)
          LX.append(0)
          LY.append(0)
          S1 = S(X,Y,P,LX,LY)
          #print(S1)
          if S1 < S0:
            S0 = S1
  ans[i] = S0
for i in range(N):
  print(ans[i+1])
print(0)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, product

N = int(input())
XYP = []
INF = 10**12

def dis(x, y):
  dist = INF
  for i in Tx:
    dist = min(dist, abs(x-i))
  for j in Ty:
    dist = min(dist, abs(y-j))
  return dist

for _ in range(N):
  X, Y, P = map(int, input().split())
  XYP.append((X, Y, P))

ans = INF

for K in range(N+1):
  for T_lis in combinations(range(N), K):
    for xy in product(range(2), repeat = K):
      temp = 0
      Tx = [0]
      Ty = [0]
      for i in range(K):
        if xy[i] == 0:
          Tx.append(XYP[T_lis[i]][xy[i]])
        else:
          Ty.append(XYP[T_lis[i]][xy[i]])
      for x, y, p in XYP:
      	temp += dis(x, y) * p
      ans = min(ans, temp)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N = int(input())

XYP = []
x = set()
y = set()
for _ in range(N):
    X, Y, P = map(int, input().split())
    if X == 0 or Y == 0:
        continue
    x.add(X)
    y.add(Y)
    XYP.append((X, Y, P))

S = float('inf')
for K in range(N + 1):
    if S != 0:
        S = float('inf')
        for k in range(K + 1):
            for cx in combinations(x, k):
                xx = [0] + list(cx)
                for cy in combinations(y, K - k):
                    yy = [0] + list(cy)
                    t = 0
                    for X, Y, P in XYP:
                        m = float('inf')
                        for i in xx:
                            m = min(m, abs(X - i))
                        for i in yy:
                            m = min(m, abs(Y - i))
                        t += m * P
                        if t >= S:
                            break
                    S = min(S, t)
        print(S)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import itertools


n = int(input())
data = [[int(x) for x in input().split(' ')] for _ in range(n)]

# 最初に、各集落と鉄道路線の最短距離をリストとして持っておく
# 路線を追加する際に、最短距離が短くなるようであれば、リストを更新して計算
# 路線の候補は、x/y軸それぞれにリストとして持っておく
# 1つずつ試していって、最小の数値だけ記憶しておいて、最後に出力

# 最短距離リスト
shortest_list = []
for i in range(n):
    shortest_list.append(min(abs(data[i][0]),abs(data[i][1])))

# 路線候補セット
x_set = set()
y_set = set()
for i in range(n):
    x_set.add(data[i][0])
    y_set.add(data[i][1])
x_len = len(x_set)
y_len = len(y_set)
set_cnt = x_len + y_len
x_lst = list(x_set)
y_lst = list(y_set)

# 初期 S
max_len = 0
for i in range(n):
    max_len += data[i][2] * shortest_list[i]

# 
for i in range(n+1):
    if max_len == 0 or i == n:
        print(0)
    elif i == 0:
        print(max_len)
    else:
        pat = itertools.combinations(range(set_cnt), i)
        for p_list in pat:
            if max_len == 0:
                break
            sl = shortest_list.copy()
            for p in p_list:
                if p < x_len:
                    for j in range(n):
                        if abs(x_lst[p] - data[j][0]) < sl[j]:
                            sl[j] = abs(x_lst[p] - data[j][0])
                else:
                    for j in range(n):
                        if abs(y_lst[p-x_len] - data[j][1]) < sl[j]:
                            sl[j] = abs(y_lst[p-x_len] - data[j][1])
            ll = 0
            for j in range(n):
                ll += data[j][2] * sl[j]
            if max_len > ll:
                max_len = ll
        print(max_len)

Submission status: Time Limit Exceeded

Solution code:
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 = np.empty((3**N, N), np.int64)  # 建設、人 -> コスト
    dp[0] = np.minimum(np.abs(X), np.abs(Y))
    size = np.empty(3**N, np.int64)
    size[0] = 0
    for n in range(N):
        B = 3**n
        DX = np.abs(X - X[n])
        DY = np.abs(Y - Y[n])
        dp[B:2 * B] = np.minimum(dp[:B], DX)
        dp[2 * B:3 * B] = np.minimum(dp[:B], DY)
        size[B:2 * B] = size[:B] + 1
        size[2 * B:3 * B] = size[:B] + 1
    dp *= P
    ans = np.full(N + 1, 10**18, np.int64)
    for s in range(3**N):
        n = size[s]
        ans[n] = min(ans[n], dp[s].sum())
    return ans

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
xs = []
ys = []
ps = []
cities = []

for _ in range(n):
    x, y, p = map(int, input().split())
    xs.append(x)
    ys.append(y)
    ps.append(p)
    cities.append((x, y, p))


large_num = abs(sum(ps) * max(ys))
ans = [large_num] * (n + 1)

for road_num in range(n + 1):
    for xnum in range(road_num + 1):
        ynum = road_num - xnum
        for cur_xs in itertools.combinations(xs, xnum):
            for cur_ys in itertools.combinations(ys, ynum):
                distances = [min(abs(x), abs(y)) * p for x, y, p in zip(xs, ys, ps)]
                for city_idx in range(n):
                    for x in cur_xs:
                        distances[city_idx] = min(distances[city_idx], abs(xs[city_idx] - x) * ps[city_idx])
                    for y in cur_ys:
                        distances[city_idx] = min(distances[city_idx], abs(ys[city_idx] - y) * ps[city_idx])
                ans[road_num] = min(ans[road_num], sum(distances))


for v in ans:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
cities = []
for i in range(N):
    X,Y,P = map(int,input().split())
    cities.append([X,Y,P])
line = [float('inf')]*(N+1)
costs = []
for x,y,p in cities:
    costs.append(p*min(abs(x),abs(y)))
costssum = [sum(costs)]
def func(D,V,K):
    queue = []
    if V == 0:
        K -= 1
    if V == 1:
        X = cities[D][0]
        for i in range(N):
            ncost = abs(cities[i][0]-X)*cities[i][2]
            if costs[i] > ncost:
                queue.append((i,costs[i]))
                costssum[0]-=costs[i]-ncost
                costs[i] = ncost
    if V == 2:
        Y = cities[D][1]
        for i in range(N):
            ncost = abs(cities[i][1]-Y)*cities[i][2]
            if costs[i] > ncost:
                queue.append((i,costs[i]))
                costssum[0]-=costs[i]-ncost
                costs[i] = ncost
    if D == N-1:
        line[K] = min(line[K],costssum[0])
        for i,cost in queue:
            costssum[0] += cost-costs[i]
            costs[i] = cost
        return
    for i in range(3):
        func(D+1,i,K)
    for i,cost in queue:
        costssum[0] += cost-costs[i]
        costs[i] = cost

for i in range(3):
    func(0,i,N)
for i in line:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
N = int(input())
town = [list(map(int,input().split())) for i in range(N)]
X = [town[i][0] for i in range(N)]
Y = [town[i][1] for i in range(N)]
#print(X)
#rint(Y)
ans = float('inf')
for k in range(N+1):
    if ans == 0:
        print(ans)
    else:
        D = [min(abs(town[i][0]),abs(town[i][1]))*town[i][2] for i in range(N)]
        ans = sum(D)
        for l in range(k+1):
            x = list(itertools.combinations(X,l))
            y = list(itertools.combinations(Y,k-l))
            #print(x)
            #print(y)
            for a in x:
                for b in y:
                    d = copy.deepcopy(D)
                    for p in a:
                        for i in range(N):
                            d[i] = min(abs(town[i][0]-p)*town[i][2],d[i])
                    for q in b:
                        for i in range(N):
                            d[i] = min(abs(town[i][1]-q)*town[i][2],d[i])
                    #print(a,b,sum(d))
                    ans = min(ans,sum(d))
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations

def solve():
      input = sys.stdin.readline
      N = int(input())
      Ans = [10 ** 10] * (N + 1)
      Ans[0] = 0
      Res = [None] * N
      for i in range(N):
            Res[i] = [int(j) for j in input().split()]
            Ans[0] += min(abs(Res[i][0]), abs(Res[i][1])) * Res[i][2] 
      
      for i in range(N):
            minCost = Ans[0]
            for l in combinations(range(N), i + 1):
                  for bit in range(2**i+1): #0はNS, 1はEW
                        B = bit
                        cost = 0
                        NS = [0]
                        EW = [0]
                        for j in range(i + 1):
                              if B % 2 == 0: NS.append(Res[l[j]][0])
                              else: EW.append(Res[l[j]][1])
                              B //= 2
                        for j in range(N):
                              nsd, ewd = 10**10, 10**10
                              for n in NS: nsd = min(nsd, abs(n - Res[j][0]))
                              for n in EW: ewd = min(ewd, abs(n - Res[j][1]))
                              cost += min(nsd, ewd) * Res[j][2]
                        Ans[i + 1] = min(Ans[i + 1], cost)

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

      return 0

if __name__ == "__main__":
      solve()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, product


def get_time_to_nearest_line(x, y, ew_lines, ns_lines):
    ew_min = min(abs(l - y) for l in ew_lines)
    ns_min = min(abs(l - x) for l in ns_lines)
    return min(ew_min, ns_min)


def get_cost(ew_lines, ns_lines):
    return sum(
        p * get_time_to_nearest_line(x, y, ew_lines, ns_lines) for x, y, p in districts
    )


N = int(input())
districts = [list(map(int, input().split())) for _ in range(N)]
init_cost = get_cost([0], [0])
for K in range(N + 1):
    min_cost = init_cost
    for do_construct_along_ew in product([True, False], repeat=K):
        for stations in combinations(districts, K):
            ew = [0]
            ns = [0]
            for i, (x, y, p) in enumerate(stations):
                if do_construct_along_ew[i]:
                    ew.append(y)
                else:
                    ns.append(x)
            min_cost = min(min_cost, get_cost(ew, ns))
        if min_cost == 0:
            print("\n".join(["0"] * (N - K + 1)))
            exit()
    print(min_cost)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from itertools import combinations
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    X, Y, P = i2(N)
    m = 10**100
    d0 = [min(abs(X[k]), abs(Y[k]))*P[k] for k in range(N)]

    for K in range(N+1):
        for ptn in combinations(range(N), K):
            for i in range(2**K):
                d = d0[:]
                for j in range(K):
                    if (i>>j)&1:
                        for k in range(N):
                            d[k] = min(abs(X[ptn[j]]-X[k])*P[k], d[k])
                    else:
                        for k in range(N):
                            d[k] = min(abs(Y[ptn[j]]-Y[k])*P[k], d[k])
                S = sum(d)
                m = min(S, m)

        print(m)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
ttl = [i for i in range(N)]

XYP = []

for i in range(N):

    x,y,p = map(int,input().split())
    XYP.append((x,y,p))

ans = float("inf")
for K in range(0,N+1):

    for lis in itertools.combinations(ttl,K):

        for i in range(2**K):

            X = [0]
            Y = [0]

            for j in range(K):
                if 2**j & i > 0:
                    X.append(XYP[lis[j]][0])
                else:
                    Y.append(XYP[lis[j]][1])
            #print (X,Y)
            now = 0
            for j in range(N):
                nn = float("inf")
                for x in X:
                    nn = min(nn , XYP[j][2] * abs(x-XYP[j][0]))
                for y in Y:
                    nn = min(nn , XYP[j][2] * abs(y-XYP[j][1]))
                now += nn
            ans = min(ans,now)
    print (ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
X = [0]*N
Y = [0]*N
P = [0]*N
ans = [0]*(N+1)
for i in range(N):
  X[i] , Y[i] , P[i] = map(int,input().split()) 
S0 = max([max(X),max(Y)])*sum(P)  
def S(X,Y,P,LX,LY):
  s = 0
  nx = len(LX)
  ny = len(LY)
  for i in range(N):
    tempX = min([abs(X[i] - j) for j in LX])
    tempY = min([abs(Y[i] - j) for j in LY])
    d = min([tempX , tempY])
    s += d*P[i]
  return(s)  
for i in range(N+1):
  for j in range(i):
    for k in range(i - j):
      for pairx in itertools.combinations(X,j):
        for pairy in itertools.combinations(Y,k):
          LX = list(pairx)
          LY = list(pairy)
          LX.append(0)
          LY.append(0)
          S1 = S(X,Y,P,LX,LY)
          #print(S1)
          if S1 < S0:
            S0 = S1
  ans[i] = S0
for i in range(N):
  print(ans[i+1])
print(0)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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


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


x_dir = [[INF] * n for i in range(1 << n)]
y_dir = [[INF] * n for i in range(1 << n)]

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


ans = [INF] * (n + 1)
for state in itertools.product((0, 1, 2), repeat=n):
    x_bit = 0
    y_bit = 0
    cnt = 0
    for i in range(n):
        if state[i] == 1:
            x_bit |= (1 << i)
            cnt += 1
        elif state[i] == 2:
            y_bit |= (1 << i)
            cnt += 1
    tmp = 0
    for i in range(n):
        tmp += min(x_dir[x_bit][i], y_dir[y_bit][i])
    ans[cnt] = min(ans[cnt], tmp)

for res in ans:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n = int(input())
xyp = [(0, 0, 0)] * n
xs = [0] * n
ys = [0] * n
ps = [0] * n
for i in range(n):
    x, y, p = map(int, input().split())
    xs[i] = x
    ys[i] = y
    ps[i] = p
x_set = set(xs)
y_set = set(ys)
x_set_list = list(x_set)
y_set_list = list(y_set)


def solve_h(h):
    if h >= len(y_set):
        return 0
    ans = 10 ** 18
    for hs in combinations(y_set_list, h):
        hs = list(hs)
        if not 0 in hs:
            hs.append(0)
        tmp = 0
        for i in range(n):
            y = ys[i]
            nearest = 10 ** 18
            for hl in hs:
                nearest = min(nearest, abs(y - hl))
            tmp += nearest * ps[i]
        ans = min(ans, tmp)
    return ans

def solve_v(v):
    if v >= len(x_set):
        return 0
    ans = 10 ** 18
    for vs in combinations(x_set_list, v):
        vs = list(vs)
        if not 0 in vs:
            vs.append(0)
        tmp = 0
        for i in range(n):
            x = xs[i]
            nearest = 10 ** 18
            for vl in vs:
                nearest = min(nearest, abs(x - vl))
            tmp += nearest * ps[i]
        ans = min(ans, tmp)
    return ans


def solve(k):
    ans = 10 ** 18
    for h in range(k + 1):
        v = k - h
        if v >= len(x_set) or h >= len(y_set):
            return 0
        for vs in combinations(x_set_list, v):
            for hs in combinations(y_set_list, h):
                tmp = 0
                vs = list(vs)
                hs = list(hs)
                if not 0 in vs:
                    vs.append(0)
                if not 0 in hs:
                    hs.append(0)
                for i in range(n):
                    nearest = 10 ** 18
                    for vl in vs:
                        nearest = min(nearest, abs(xs[i] - vl))
                    for hl in hs:
                        nearest = min(nearest, abs(ys[i] - hl))
                    tmp += nearest * ps[i]
                ans = min(ans, tmp)
    return ans


for k in range(n + 1):
    print(solve(k))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

for k in range(n):
    if k == 0:
        dist = 0
        for i in range(n):
            dist += min(abs(a[i]), abs(b[i])) * p[i]
        print(dist)
    else:
        min_dist = dist
        if min_dist==0:
            print(0)
        else:
            for l in itertools.combinations(range(n), k):
                for m in itertools.product(range(2), repeat=k):
                    yoko_list = [0]
                    tate_list = [0]
                    for i in range(k):
                        if m[i] == 0:
                            yoko_list.append(b[l[i]])
                        else:
                            tate_list.append(a[l[i]])
                    dist = 0
                    for i in range(n):
                        if i in l:
                            pass
                        else:
                            yoko_min = min([abs(a[i] - j) for j in tate_list])
                            tate_min = min([abs(b[i] - j) for j in yoko_list])
                            dist += min(yoko_min, tate_min) * p[i]
                    if min_dist > dist:
                        min_dist = dist
            print(min_dist)
print(0)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import combinations
    import bisect
    N = int(input())
    XYP = [tuple(map(int, input().split())) for i in range(N)]

    S = 0
    for x, y, p in XYP:
        S += min(abs(x), abs(y))*p

    print(S)

    dpX = [[0]*N for i in range(2**N)]

    dpY = [[0]*N for i in range(2**N)]

    for i in range(2**N):
        arr = []
        for j in range(N):
            if (i >> j) % 2 == 1:
                if (len(arr) == 0 or arr[-1] < 0) and XYP[j][0] > 0:
                    arr.append(0)
                arr.append(XYP[j][0])

        for j in range(N):
            if (i >> j) % 2 == 1:
                dpX[i][j] = 0
            else:
                X = XYP[j][0]
                id = bisect.bisect_left(arr, X)
                ret = abs(X)
                if id < len(arr):
                    ret = min(ret, arr[id] - X)
                if id > 0:
                    ret = min(ret, X - arr[id-1])
                dpX[i][j] = ret * XYP[j][2]

    for i in range(2**N):
        arr = []
        for j in range(N):
            if (i >> j) % 2 == 1:
                if (len(arr) == 0 or arr[-1] < 0) and XYP[j][1] > 0:
                    arr.append(0)
                arr.append(XYP[j][1])

        for j in range(N):
            if (i >> j) % 2 == 1:
                dpY[i][j] = 0
            else:
                Y = XYP[j][1]
                id = bisect.bisect_left(arr, Y)
                ret = abs(Y)
                if id < len(arr):
                    ret = min(ret, arr[id] - Y)
                if id > 0:
                    ret = min(ret, Y - arr[id-1])
                dpY[i][j] = ret * XYP[j][2]

    for i in range(1, N+1):
        if S > 0:
            for j in range(i+1):
                k = i - j
                for x in combinations(range(N), j):
                    idx = 0
                    for xx in x:
                        idx += 1 << xx
                    dX = dpX[idx]
                    for y in combinations(range(N), k):

                        tmp = 0
                        idy = 0
                        for yy in y:
                            idy += 1 << yy
                        # print(j, k, dX, dpY[idy])
                        for l in range(N):
                            if dX[l] > dpY[idy][l]:
                                tmp += dpY[idy][l]
                            else:
                                tmp += dX[l]
                        if S > tmp:
                            S = tmp
        print(S)


main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import bisect
n=int(input())
data=list(range(2*n))
a=[]
for _ in range(n):
  a+=[list(map(int,input().split()))]
for i in range(n+1):
  fans=10**18
  for j in list(combinations(data,i)):
    x,y=[0],[0]
    for k in j:
      if k%2:x+=[a[k//2][0]]
      else:y+=[a[k//2][1]]
    x=[-10**18]*2+sorted(x)+[10**18]
    y=[-10**18]*2+sorted(y)+[10**18]
    ans=0
    for k in range(n):
      xi=bisect.bisect_left(x,a[k][0])
      yi=bisect.bisect_left(y,a[k][1])
      ans+=min(min(abs(a[k][0]-x[xi-1]),abs(a[k][0]-x[xi]))*a[k][2],
               min(abs(a[k][1]-y[yi-1]),abs(a[k][1]-y[yi]))*a[k][2])
    fans=min(fans,ans)
  print(fans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


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)

def get_cands(cost, axis):
    cands = set()
    for i in range(N):
        if cost[i] != 0:
            cands.add(axis[i])
    return cands

def update_cost(cost, x, axis):
    cost = list(cost)
    for i in range(N):
        cost[i] = min(cost[i], P[i] * abs(axis[i]-x))
    return tuple(cost)

cost = tuple([P[i] * min(abs(X[i]), abs(Y[i])) for i in range(N)])
print(sum(cost))
costs = {cost}

for k in range(N):
    new_costs = set()
    for cost in costs:
        for x_cand in get_cands(cost, X):
            new_costs.add(update_cost(cost, x_cand, X))
        for y_cand in get_cands(cost, Y):
            new_costs.add(update_cost(cost, y_cand, Y))

    costs = new_costs
    if not costs:
        print(0)
    else:
        print(min([sum(cost) for cost in costs]))