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
from itertools import combinations
input = sys.stdin.buffer.readline
N = int(input())
cities = []
for _ in range(N):
    X, Y, P = map(int, input().split())
    cities.append((X, Y, P))
# print(f'{cities}')


def f(x0, y0, x1, y1, x2, y2):
    a = x2 - x1
    b = y2 - y1
    a2 = a * a
    b2 = b * b
    r2 = a2 + b2
    tt = -(a * (x1 - x0) + b * (y1 - y0))
    if tt < 0:
        return (x2 - x0) * (x2 - x0) + (y2 - y0) * (y2 - y0)
    f1 = a * (y1 - y0) - b * (x1 - x0)
    return (f1 * f1) / r2


MARGIN = 30000

S = 10**50
for K in range(N):
    gt = combinations(range(N * 2), K)
    for combi in gt:
        # print(f'{combi=}')
        do = True
        for i in range(len(combi) - 1):
            for j in range(i + 1, len(combi)):
                if combi[i] + N == combi[j]:
                    do = False
                    break
            if not do:
                break
        if not do:
            # print(f'continue {combi}')
            continue
        # print(f'end {combi=}')
        XY = []
        XY.append((-MARGIN, 0, MARGIN, 0))
        XY.append((0, -MARGIN, 0, MARGIN))
        for i in combi:
            x, y, p = cities[i % N]
            if i < N:
                # yoko
                x1, y1 = x - MARGIN, y
                x2, y2 = x + MARGIN, y
                XY.append((x1, y1, x2, y2))
            else:
                # tate
                x1, y1 = x, y - MARGIN
                x2, y2 = x, y + MARGIN
                XY.append((x1, y1, x2, y2))
        # print(f'{XY=}')

        _S = 0
        for i in range(N):
            x0, y0, p = cities[i]
            d = 10**20
            for x1, y1, x2, y2 in XY:
                d = min(d, f(x0, y0, x1, y1, x2, y2))
            # print(f'd={round(d**0.5)}')
            _S += round(d**0.5) * p
        S = min(S, _S)
        # print(f'{S=}')
    # print(f'for out {S=}')
    print(S)
    if S == 0:
        # print('test')
        for i in range(N - K):
            print(0)
        exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

ans = [10 ** 18] * (N+1)
for how_to_build in product(range(3), repeat = N):
    xs = [0]
    ys = [0]
    k = 0
    for i, h in enumerate(how_to_build):
        if h == 1:
            k += 1
            xs.append(XYPs[i][0])
        elif h == 2:
            k += 1
            ys.append(XYPs[i][1])
    walksum = 0
    for X, Y, P in XYPs:
        mindis = min(min([abs(X - x) for x in xs]), min([abs(Y - y) for y in ys]))
        walksum += mindis * P
    ans[k] = min(ans[k], walksum)
print(*ans, sep = '\n')

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
t = [[0]*3 for _ in range(N)]
for i in range(N):
    t[i][0],t[i][1],t[i][2] = map(int,input().split())

dis = [[[0]*2 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        dis[i][j][0] = abs(t[i][0]-t[j][0])
        dis[i][j][1] = abs(t[i][1]-t[j][1])
#print(dis)

ans = [[] for _ in range(N+1)]
K = 3 # 選択肢の数
for i in range(K**N):
    TF=[0]*N

    for j in range(N):
        TF[N-j-1] = i % K
        i //= K
    
    #print(TF)
    tate,yoko = [],[]
    for i in range(N):
        if TF[i] == 1:
            tate.append(i)
        if TF[i] == 2:
            yoko.append(i)
    #print(tate,yoko)

    distance = 0
    for i in range(N):
        tmp = [min(abs(t[i][0]),abs(t[i][1]))]
        for j in tate:
            tmp.append(dis[i][j][0])
        for j in yoko:
            tmp.append(dis[i][j][1])
        if tmp:
            distance += t[i][2] * min(tmp)
        else:
            distance += t[i][2] * min(abs(t[i][0]),abs(t[i][1]))
    road = len(set(tate))+len(set(yoko))
    #print(road,distance)
    ans[road].append(distance)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
#print(a)
tableud = [[0] * N for _ in range(N)]
tablelr = [[0] * N for _ in range(N)]
for i in range(N):
  x, y, _ = a[i]
  for j in range(N):
    tableud[i][j] = abs(a[j][0] - x) * a[j][2]
    tablelr[i][j] = abs(a[j][1] - y) * a[j][2]
zero = 0
for t in range(N + 1):
  res = float("inf")
  if zero:
    print(0)
    continue
  for c in combi([x for x in range(N)], t):
    for i in range(1 << t):
      table = [10 ** 20] * N
      for j in range(N):
        table[j] = min(abs(a[j][0]), abs(a[j][1])) * a[j][2]
      for j in range(t):
        if i & (1 << j):
          for k in range(N):
            table[k] = min(table[k], tableud[c[j]][k])
        else:
          for k in range(N):
            table[k] = min(table[k], tablelr[c[j]][k])
      res = min(res, sum(table))
  print(res)
  if res == 0: zero = 1

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):
            Ans[i + 1] = Ans[i]
            for l in combinations(range(N), i + 1):
                  if Ans[i+1] == 0: break
                  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):
                              d = 10 ** 10
                              for n in NS: d = min(d, abs(n - Res[j][0]))
                              for n in EW: d = min(d, abs(n - Res[j][1]))
                              cost += d * Res[j][2]
                        Ans[i + 1] = min(Ans[i + 1], cost)
                        if cost == 0: break
                  

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

      return 0

if __name__ == "__main__":
      solve()

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import defaultdict

N = int(input())
Cities = [list(map(int, input().split())) for i in range(N)]
Distances = Cities.copy()
ans = defaultdict(lambda: float('inf'))
comb = list(itertools.product(range(3),repeat=N))

def calc(direction):
    x_list = list(direction['x'])
    y_list = list(direction['y'])
    ans = 0
    for c in Cities:
        x, y, p = c
        res = float('inf')
        for i in x_list:
            res = min(res, abs(x-i))
        for j in y_list:
            res = min(res, abs(y-j))
        ans += res*p
    return ans


for c in comb:
    direction = {'x':{0}, 'y':{0}}
    k = 0
    for i in range(N):
        x, y, p = Cities[i]
        if c[i]:
            k += 1
            if c[i] == 1:
                direction['x'].add(x)
            else:
                direction['y'].add(y)
    ans[k] = min(ans[k], calc(direction))

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

Submission status: Time Limit Exceeded

Solution code:
def score(CITIES, lines):
    s = 0
    for c in CITIES:
        x = c[0]
        y = c[1]
        p = c[2]

        min_dist = 1000000000000
        for l in lines:
            if l[1] == "H":
                dist = abs(y-l[0])
            else:
                dist = abs(x-l[0])
            min_dist = min(min_dist, dist)
        s += min_dist * p
    return s

def recursive_score(K, CITIES, candidate_lines, selected):
    if len(selected) == K:
        lines = [[0, "H"], [0, "V"]]
        for s in selected:
            lines.append(candidate_lines[s])
        return score(CITIES, lines)

    min_score = 1000000000000
    for i in range(len(candidate_lines)):
        if i in selected:
            continue
        sel = selected + [i]
        s = recursive_score(K, CITIES, candidate_lines, sel)
        min_score = min(min_score, s)
    return min_score

def main():
    N = int(input())
    CITIES = []

    for i in range(N):
        # x=c[0]
        # y=c[1]
        # p=c[2]
        c = [int(_x) for _x in input().split()]
        CITIES.append(c)

    candidate_lines = []
    for i in range(N):
        candidate_lines.append([CITIES[i][1], "H"])  # y座標が同じで横線
        candidate_lines.append([CITIES[i][0], "V"])  # x座標が同じで縦線

    for K in range(N+1):
        S = recursive_score(K, CITIES, candidate_lines, [])
        print(S)

main()

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(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]
                    if tmp > ans:
                        break
                ans = min(ans, tmp)
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
n = int(input())

x = []
y = []
p = []
for i in range(n):
    xx,yy,pp = map(int,input().split())
    x.append(xx+10000)
    y.append(yy+10000)
    p.append(pp)

def iter_p_adic(p, n):

    tmp = [range(p)] * n
    return product(*tmp)

res = [10**20]*(n+1)


iterator = iter_p_adic(3,n)
for idxs in iterator:
    yoko = set([10000])
    tate = set([10000])
    
    for i in range(n):
        if idxs[i] == 1:
            yoko.add(y[i])
        elif idxs[i] == 2:
            tate.add(x[i])

    tmp = 0
    for i in range(n):
        if idxs[i] == 0:
            mi = 10**9
            for e in yoko:
                if mi > abs(e-y[i]):
                    mi = abs(e-y[i])
            for e in tate:
                if mi > abs(e-x[i]):
                    mi = abs(e-x[i])
            tmp += p[i]*mi

    residx = len(yoko) + len(tate) - 2
    if tmp == 0 and res[residx] != 0:
        for j in range(residx,n+1):
            res[j] = 0
    elif residx < n+1 and res[residx] > tmp:
        res[residx] = tmp
for e in res:
    print(e)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

towns = []
xs = []
ys = []
for i in range(n):
    t = tuple(map(int, input().split()))
    towns.append(t)
    xs.append(t[0])
    ys.append(t[1])

memo = dict()
def calculate_cost(railX, railY):
    rails = [str(rail) for rail in railX + railY]
    current_key = ','.join(rails)
    if len(memo) > 0:
        if current_key in memo:
            return memo[current_key]
    sumCost = 0
    for x, y, p in towns:
        minX = min([abs(x - X) for X in railX])
        minY = min([abs(y - Y) for Y in railY])
        cost = min(minX, minY)
        sumCost += (cost * p)

    memo.update({current_key: sumCost})
    return sumCost

import itertools

prev = 1
for k in range(n+1):
    if prev == 0:
        print(0)
        continue
    xCandidate = ['X' + str(x) for x in set(xs)]
    yCandidate = ['Y' + str(y) for y in set(ys)]
    comb = list(itertools.combinations(xCandidate+yCandidate, k))

    candidate = []
    ans = 0
    for c in comb:
        railX = [0]
        railY = [0]

        for r in c:
            if r[0] == 'X':
                railX.append(int(r.replace('X', '')))
            elif r[0] == 'Y':
                railY.append(int(r.replace('Y', '')))
        result = calculate_cost(railX, railY)

        if len(candidate) > 0:
            minV = min(candidate)
            ans = min(minV, result)
            if not (ans in candidate):
                candidate.append(ans)
        else:
            ans = result
            candidate.append(result)

    print(ans)
    prev = ans

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations, combinations,combinations_with_replacement,product
n = int(input())
syuraku = [tuple(map(int,input().split())) for i in range(n)]
manzoku = [-1 for i in range(n)]
now = 0
for i in range(n):
    manzoku[i] = min(abs(syuraku[i][0]),abs(syuraku[i][1]))
    now += manzoku[i]*syuraku[i][2]
print(now)
kazu = [i for i in range(n)]
for k in range(1,n+1):
    ans = now
    kouho = list(combinations(kazu,k))
    for p in kouho:
        for i in range(2**k):
            cou = 0
            kar = manzoku[:]
            for j in range(k):
                kar[p[j]] = 0
            for j in range(k):
                for t in range(n):
                    if kar[t] == 0:
                        continue
                    s = i >> j & 1
                    kar[t] = min(kar[t],abs(syuraku[t][s] - syuraku[p[j]][s]))
            for j in range(n):
                cou += kar[j] * syuraku[j][2]
            ans = min(ans,cou)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def CalcCost(xtrain, ytrain):
    cost = 0
    for x,y,p in town:
        # print("x,y,p", x,y,p)
        tmp = float("inf")
        for tx in xtrain:
            tmp = min(tmp, abs(x-tx)*p)
        for ty in ytrain:
            tmp = min(tmp, abs(y-ty)*p)
        cost += tmp
        # print("costx", costx, "costy", costy)
    return cost

n = int(input())
town = []
xtown, ytown = [], []
for _ in range(n):
    x,y,p = map(int, input().split())
    town.append((x,y,p))
    xtown.append(x)
    ytown.append(y)

xtrain = [0]
ytrain = [0]

print(CalcCost(xtrain, ytrain))


for i in range(1, n+1):
    ans = float("inf")
    indx = -1
    indy = -1
    # print("i", i)
    for j in range(i+1):
        # print("j",j)
        for xl in combinations(xtown, j):
            xtrain_c = xtrain.copy()

            xtrain_c += xl
            # xcost = CalcCost(xtrain_c, ytrain)
            # # print("x",xcost)
            # if ans > xcost:
            #     ans = xcost

            for yl in combinations(ytown, i-j):
                ytrain_c = ytrain.copy()
                ytrain_c += yl
                # print("xtr_c", xtrain_c)
                # print("ytr_c", ytrain_c)


                ycost = CalcCost(xtrain_c, ytrain_c)
                # print("y", ycost)
                if ans > ycost:
                    ans = ycost

    print(ans)
    # if indx == -1:
    #     ytrain.append(town[indy][1])
    # else:
    #     xtrain.append(town[indx][0])
    # print("xtr", xtrain)
    # print("ytr", ytrain)

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 = min(min(abs(X - i) for i in xx), min(abs(Y - i) for i in yy))
                        t += m * P
                        if t >= S:
                            break
                    S = min(S, t)
                    if S == 0:
                        break
                if S == 0:
                    break
            if S == 0:
                break
        print(S)
    else:
        print(0)

Submission status: Time Limit Exceeded

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

N=int(input())
P=[list(map(int,input().split())) for i in range(N)]
ANS=1<<60

for rail in range(N-1):
    I=combinations(list(range(N)),rail)

    for rails in I:
        #print(rails)
        if ANS==0:
            break

        for i in range(1<<rail):
            X=[0]
            Y=[0]
            for j in range(rail):
                if (1<<j) & i ==0:
                    X.append(P[rails[j]][0])
                else:
                    Y.append(P[rails[j]][1])

            C=0
            for x,y,p in P:
                MIN=1<<30
                for xx in X:
                    MIN=min(abs(xx-x),MIN)
                for yy in Y:
                    MIN=min(abs(yy-y),MIN)

                C+=MIN*p
                if C>=ANS:
                    break

            #print(X,Y,C)

            ANS=min(ANS,C)

    print(ANS)

ANS=1<<60
for x,y,c in P:
    ANS=min(ANS,abs(x)*c,abs(y)*c)
    for xx,yy,cc in P:
        if x==xx and y==yy:
            continue
        ANS=min(ANS,abs(x-xx)*c,abs(y-yy)*c)

print(ANS)
print(0)

Submission status: Time Limit Exceeded

Solution code:

def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


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]

    ans = [S]*N

    for i in range(2**N):
        pc = popcount(i)
        for j in range(2**N):
            count = pc + popcount(j)
            if count > N:
                continue

            dX = dpX[i]
            dY = dpY[j]
            tmp = 0
            for x, y in zip(dX, dY):
                if x > y:
                    tmp += y
                else:
                    tmp += x
            if tmp < ans[count-1]:
                ans[count-1] = tmp

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    tot=0
    base=[0]*N
    for i,(x,y,p) in enumerate(S):
        ta=min(abs(x),abs(y))*p
        base[i]=ta
        tot+=ta

    print(tot)
    inf=tot
    ts=list(range(N))
    for i in range(1,N+1):
        ans=inf
        for t in combinations(ts,i):
            t=list(t)
            sea=set()
            for j in range(N):
                if j not in t:
                    sea.add(j)
            for j in range(2**i):
                l=copy(base)

                for k in range(i):
                    if (j>>k)&1:
                        for li in sea:
                            l[li]=min(l[li],abs(S[li][1]-S[t[k]][1])*S[li][2])
                    else:
                        for li in sea:
                            l[li]=min(l[li],abs(S[li][0]-S[t[k]][0])*S[li][2])
                tot=0

                for s in sea:
                    tot+=l[s]
                ans=min(ans,tot)
        print(ans)
                
                
    




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations, product

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8[:],i8[:],i8[:],i8[:],i8[:])", cache=True)
def calc_S(X, Y, P, x_paths, y_paths):
    S = 0
    for x, y, p in zip(X, Y, P):
        min_path = min(min(np.abs(x - x_paths)), min(np.abs(y - y_paths)))
        S += p * min_path
    return S


def main():
    N = int(input())
    X = np.zeros(shape=N, dtype=np.int64)
    Y = np.zeros(shape=N, dtype=np.int64)
    P = np.zeros(shape=N, dtype=np.int64)
    for i in range(N):
        X[i], Y[i], P[i] = map(int, input().split())

    ans = [0] * (N + 1)
    x_paths = np.zeros(1, dtype=np.int64)
    y_paths = np.zeros(1, dtype=np.int64)
    ans[0] = calc_S(X, Y, P, x_paths, y_paths)
    for K in range(1, N + 1):
        S_min = float("inf")
        for paths in combinations(range(N), K):
            for directions in product(range(2), repeat=K):
                x_paths = np.zeros(1, dtype=np.int64)
                y_paths = np.zeros(1, dtype=np.int64)
                for path, direction in zip(paths, directions):
                    if direction == 0:
                        x_paths = np.append(x_paths, X[path])
                    else:
                        y_paths = np.append(y_paths, Y[path])
                S = calc_S(X, Y, P, x_paths, y_paths)
                if S < S_min:
                    S_min = S
        ans[K] = S_min

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


if __name__ == "__main__":
    main()

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)) * P
    size = np.empty(3**N, np.int64)
    size[0] = 0
    for n in range(N):
        B = 3**n
        DX = np.abs(X - X[n]) * P
        DY = np.abs(Y - Y[n]) * P
        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
    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:
from itertools import permutations, combinations,combinations_with_replacement,product
n = int(input())
syuraku = [tuple(map(int,input().split())) for i in range(n)]
manzoku = [-1 for i in range(n)]
now = 0
for i in range(n):
    manzoku[i] = min(abs(syuraku[i][0]),abs(syuraku[i][1]))
    now += manzoku[i]*syuraku[i][2]
print(now)
kazu = [i for i in range(n)]
for k in range(1,n+1):
    ans = now
    kouho = list(combinations(kazu,k))
    for p in kouho:
        for i in range(2**k):
            cou = 0
            kar = manzoku[:]
            for j in range(k):
                for t in range(n):
                    s = i >> j & 1
                    kar[t] = min(kar[t],abs(syuraku[t][s] - syuraku[p[j]][s]))
            for j in range(n):
                cou += kar[j] * syuraku[j][2]
            ans = min(ans,cou)
    print(ans)