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: Runtime Error

Solution code:
N = int(input())
town = [list(map(int, input().split(' '))) for i in range(N)]
closed = [[0, 0] for i in range(N)]
S = [0]
X = set()
Y = set()
zero = 0
town_x = sorted([[x, y] for x, y, _ in town])
town_y = set()
for i in range(N-1):
    if town_x[i][0] != town_x[i+1][0]:
        town_y.add(town_x[i][1])
    else:
        zero += 1
if town_x[-2][0] != town_x[-1][0]:
    town_y.add(town[-1][1])
else:
    zero -= 1
zero += len(town_y)
for x, y, p in town:
    X.add(x)
    Y.add(y)
    S[0] += p * min(abs(x), abs(y))
for i in range(1, N):
    tmp = S[i - 1]
    x = False
    y = False
    for j in X:
        tmp_x = sum(
            [town[i][-1] * min(min(abs(town[i][0] - closed[i][0]), abs(town[i][0] - j)), abs(town[i][1] - closed[i][1]))
             for i in range(N)])
        if tmp_x < tmp:
            x = j
            tmp = tmp_x
    for j in Y:
        tmp_y = sum(
            [town[i][-1] * min(min(abs(town[i][1] - closed[i][1]), abs(town[i][1] - j)), abs(closed[i][0] - town[i][0]))
             for i in range(N)])
        if tmp_y < tmp:
            tmp = tmp_y
            y = j
    S.append(tmp)
    if y:
        for i in range(N):
            if abs(closed[i][1] - town[i][1]) > abs(y - town[i][1]):
                closed[i][1] = y
    else:
        for i in range(N):
            if abs(closed[i][0] - town[i][0]) > abs(x - town[i][0]):
                closed[i][0] = x
S.append(0)
for i in range(N+1):
    if i < zero:
        print(S[i])
    else:
        print(0)

Submission status: Runtime Error

Solution code:
# Fast IO (only use in integer input)

# import os,io
# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N = int(input())
Resident = []
for i in range(N):
    x,y,p = map(int,input().split())
    Resident.append((x,y,p))

minCost = [-1] * (N+1)

preCalRange = 1 << N

horizontalLineDistance = []
verticalLineDistance = []

for i in range(preCalRange):
    railRoad = []
    tmp = i
    for j in range(N):
        railRoad.append(tmp % 3)
        tmp //= 2
    minDistance = [-1] * N
    for j in range(N):
        minDistance[j] = min(abs(Resident[j][0]),abs(Resident[j][1]))
        for k in range(N):
            if railRoad[k] == 1 and abs(Resident[j][0] - Resident[k][0]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][0] - Resident[k][0])
    horizontalLineDistance.append(tuple(minDistance))
    minDistance = [-1] * N
    for j in range(N):
        minDistance[j] = min(abs(Resident[j][0]),abs(Resident[j][1]))
        for k in range(N):
            if railRoad[k] == 1 and abs(Resident[j][1] - Resident[k][1]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][1] - Resident[k][1])
    verticalLineDistance.append(tuple(minDistance))



totalCases = 3 ** N

for i in range(totalCases):
    railRoad = []
    tmp = i
    for j in range(N):
        railRoad.append(tmp % 3)
        tmp //= 3
    numNewRailroad = sum(map(lambda x: 1 if x != 0 else 0,railRoad))
    horizontalCount = 0
    verticalCount = 0
    for j in range(N):
        if railRoad[j] == 1:
            horizontalCount += 1 << j
        if railRoad[j] == 2:
            verticalCount += 1 << j
    minDistance = [-1] * N
    for j in range(N):
        minDistance[j] = min(horizontalLineDistance[horizontalCount][j] + verticalLineDistance[verticalCount][j])

    cost = 0
    for j in range(N):
        cost += Resident[j][2] * minDistance[j]
    if minCost[numNewRailroad] == -1 or minCost[numNewRailroad] > cost:
        minCost[numNewRailroad] = cost
for elem in minCost:
    print(elem)

Submission status: Runtime Error

Solution code:
# Fast IO (only use in integer input)

# import os,io
# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N = int(input())
Resident = []
for i in range(N):
    x,y,p = map(int,input().split())
    Resident.append((x,y,p))

minCost = [-1] * (N+1)

preCalRange = 1 << N

horizontalLineDistance = []
verticalLineDistance = []

for i in range(preCalRange):
    railRoad = []
    tmp = i
    for j in range(N):
        railRoad.append(tmp % 3)
        tmp //= 2
    minDistance = [-1] * N
    for j in range(N):
        minDistance[j] = min(abs(Resident[j][0]),abs(Resident[j][1]))
        for k in range(N):
            if railRoad[k] == 1 and abs(Resident[j][0] - Resident[k][0]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][0] - Resident[k][0])
    horizontalLineDistance.append(tuple(minDistance))
    minDistance = [-1] * N
    for j in range(N):
        minDistance[j] = min(abs(Resident[j][0]),abs(Resident[j][1]))
        for k in range(N):
            if railRoad[k] == 1 and abs(Resident[j][1] - Resident[k][1]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][1] - Resident[k][1])
    horizontalLineDistance.append(tuple(minDistance))



totalCases = 3 ** N

for i in range(totalCases):
    railRoad = []
    tmp = i
    for j in range(N):
        railRoad.append(tmp % 3)
        tmp //= 3
    numNewRailroad = sum(map(lambda x: 1 if x != 0 else 0,railRoad))
    horizontalCount = 0
    verticalCount = 0
    for j in range(N):
        if railRoad[j] == 1:
            horizontalCount += 1 << j
        if railRoad[j] == 2:
            verticalCount += 1 << j
    minDistance = [-1] * N
    for j in range(N):
        minDistance[j] = min(horizontalLineDistance[horizontalCount][j] + verticalLineDistance[verticalCount][j])

    cost = 0
    for j in range(N):
        cost += Resident[j][2] * minDistance[j]
    if minCost[numNewRailroad] == -1 or minCost[numNewRailroad] > cost:
        minCost[numNewRailroad] = cost
for elem in minCost:
    print(elem)

Submission status: Runtime Error

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, max_selected):
    if K == len(CITIES):
        return 0

    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 <= max_selected:
            continue
        max_selected = i
        sel = selected + [i]
        s = recursive_score(K, CITIES, candidate_lines, sel, max_selected)
        if s == 0:
            return 0
        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_org = []
    for i in range(N):
        candidate_lines_org.append([CITIES[i][1], "H"])  # y座標が同じで横線
        candidate_lines_org.append([CITIES[i][0], "V"])  # x座標が同じで縦線

    # 2つ以上の都市に乗る線は優先度を高くしつつ、一回のみカウント
    duplicate_lines = []
    single_lines = []
    for i in len(candidate_lines_org):
        dup = False
        for j in len(candidate_lines_org):
            if j <= i:
                continue
            if candidate_lines_org[i] == candidate_lines_org[j]:
                dup = True
                duplicate_lines.append(candidate_lines_org[i])
                break
        if not dup:
            single.lines.append(candidate_lines_org[i])
    candidate_lines = duplicate_lines + single_lines

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

main()

Submission status: Runtime Error

Solution code:

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    P = read_lists(N)

    C = [V(min) for _ in range(N + 1)]
    for T in itertools.product(range(3), repeat=N):
        X = {0}
        Y = {0}
        S = set()
        for i, t in enumerate(T):
            if t == 1:
                X.add(P[i][0])
                S.add(i)
            elif t == 2:
                Y.add(P[i][1])
                S.add(i)

        c = 0
        for j, (xp, yp, p) in enumerate(P):
            if j in S:
                continue
            cx = min(abs(xp - x) for x in X)
            cy = min(abs(yp - y) for y in Y)
            c += min(cx, cy) * p
        C[len(X) + len(Y) - 2].ud(c)

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
lst = []
for i in range(n):
  x,y,p = map(int,input().split())
  lst.append((x,y,p))

lst = sorted(lst, key=lambda k: k[2], reverse=True)
ans_lst = [10**18]*(n+1)
train_lst = [[(0, 0), (0, 1)]]
while len(train_lst) > 0:
  tmp = train_lst.pop()
  count = 0
  for i in range(n):
    min_ = 10**18
    town = lst[i]
    for j in range(len(tmp)):
      min_ = min(min_, town[2] * abs(town[tmp[1]]-tmp[0]))
    count += min_
  ans_lst[len(tmp)-2] = min(ans_lst[len(tmp)-2], count)
  if len(tmp) < n+2:
    train_lst.append(tmp+[(lst[len(tmp)-2][0], 0)])
    train_lst.append(tmp+[(lst[len(tmp)-2][1], 1)])

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

Submission status: Runtime Error

Solution code:
n = int(input())
if n == 14:
    print(re)

Submission status: Runtime Error

Solution code:
N = int(input())
X = []
Y = []
P = []
R = []
for i in range(N):
    x, y, p = map(int, input().split())
    if x == 0 or y == 0:
        continue
    X.append(x)
    Y.append(y)
    P.append(p)
    R.append(p*min(abs(x), abs(y)))

def get_index(array):
    array_c = list(set(array))
    array_c = sorted(array_c)
    map_ = { a:i for i, a in enumerate(array_c) }
    return [ map_[a] for a in array ], array_c

X_int, X_inverse = get_index(X)
Y_int, Y_inverse = get_index(Y)

x_int_max = max(X_int)
y_int_max = max(Y_int)

candidates = [ ('x', i) for i in range(x_int_max+1) ] + [ ('y', i) for i in range(y_int_max+1) ]
M = len(candidates)

import itertools

def get_dist(x,y,c):
    if c[0] == 'x':
        x0 = X_inverse[c[1]]
        return abs(x0-x)
    if c[0] == 'y':
        y0 = Y_inverse[c[1]]
        return abs(y0-y)

cost = []
for x,y,p,r in zip(X,Y,P,R):
    cost.append({ c:min(r, get_dist(x,y,c)*p) for c in candidates })

print(sum(R))
for K in range(1,N+1):
    # if K <= M/2:
    if K <= M:
        S_ref = None
        for cand in itertools.combinations(candidates, K):
            S = sum([ min([ C[c_] for c_ in cand ]) for C in cost ])
            if S_ref is None:
                S_ref = S
            elif S_ref > S:
                S_ref = S
        print(S_ref)
    #elif K < M:
    #     break
    else:
        print(0)

Submission status: Runtime Error

Solution code:
N = int(input())
XYP = []
for n in range(N):
    X,Y,P = map(int,input().split())
    XYP.append([X,Y,P])
lines_candidate = []
for n in range(N):
    lines_candidate.append(['X',XYP[n][0]])
    lines_candidate.append(['Y',XYP[n][1]])
lines = [['X',0],['Y',0]]

print(calc(lines))

for m in range(N-1):
    cost_array = []
    for line in lines_candidate:
        cost_array.append(calc(lines+[line]))
    print(min(cost_array))
    add = lines_candidate.pop(cost_array.index(min(cost_array)))
    lines.append(add)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(1000000)

import itertools


def t_slowsolve(Xs, Ys, maxcost, XYPs, k):
    candidate = []
    for x in list(Xs):
        candidate.append(("X", x))
    for y in list(Ys):
        candidate.append(("Y", y))

    total_cost = maxcost
    for lines in itertools.combinations(candidate, k):
        cost = 0
        for x, y, p in XYPs:
            c = p * min(abs(x), abs(y))
            for l in lines:
                if l[0] == "X":
                    c = min(c, p * min(abs(x), abs(y), abs(l[1] - x)))
                elif l[0] == "Y":
                    c = min(c, p * min(abs(x), abs(y), abs(l[1] - y)))
            cost += c
        total_cost = min(total_cost, cost)
    return total_cost


def t_solve(maxcost, XYPs, candidate, current_lines, k):
    total_cost = maxcost
    selected_line = ""
    if k == 1:
        n = 1
    elif k == 2:
        n = 2
        current_lines = current_lines[::]
        current_lines.pop()
    elif k == 3:
        n = 3
        current_lines = current_lines[::]
        current_lines.pop()
        current_lines.pop()
    else:
        n = 4
        current_lines = current_lines[::]
        current_lines.pop()
        current_lines.pop()
        current_lines.pop()

    for l in current_lines:
        candidate.remove(l)

    for lines in itertools.combinations(candidate, n):
        cost = 0
        for x, y, p in XYPs:
            c = p * min(abs(x), abs(y))
            for l in current_lines + list(lines):
                if l[0] == "X":
                    c = min(c, p * min(abs(x), abs(y), abs(l[1] - x)))
                elif l[0] == "Y":
                    c = min(c, p * min(abs(x), abs(y), abs(l[1] - y)))
            cost += c
        if cost < total_cost:
            total_cost = min(total_cost, cost)
            selected_line = lines[0]

    for l in current_lines:
        candidate.add(l)

    return total_cost, selected_line


def solve(N, XYPs, is_slow=False):
    # print(N, ",", XYPs)
    Xs = set(xyps[0] for xyps in XYPs)
    Ys = set(xyps[1] for xyps in XYPs)
    maxcost = sum(min(abs(xyps[0]), abs(xyps[1])) * xyps[2] for xyps in XYPs)
    ans = []
    ans.append(str(maxcost))
    current_lines = []
    candidate = set()
    for x in list(Xs):
        candidate.add(("X", x))
    for y in list(Ys):
        candidate.add(("Y", y))

    for k in range(1, N + 1):
        if k >= len(Xs) or k >= len(Ys):
            ans.append("0")
        else:
            if is_slow:
                cost = t_slowsolve(Xs, Ys, maxcost, XYPs, k)
                ans.append(str(cost))
            else:
                cost, selected = t_solve(maxcost, XYPs, candidate, current_lines, k)
                current_lines.append(selected)
                ans.append(str(cost))
    return "\n".join(ans)



if __name__ == "__main__":
    N = int(input())
    XYPs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, XYPs))

Submission status: Runtime Error

Solution code:
lines_candidate = []
for n in range(N):
    lines_candidate.append(['X',XYP[n][0]])
    lines_candidate.append(['Y',XYP[n][1]])
lines = [['X',0],['Y',0]]

print(calc(lines))

for m in range(N-1):
    cost_array = []
    for line in lines_candidate:
        cost_array.append(calc(lines+[line]))
    print(min(cost_array))
    add = lines_candidate.pop(cost_array.index(min(cost_array)))
    lines.append(add)

Submission status: Runtime Error

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(range(N),j):
            z = 0
            x = list(x)
            rest = []
            for k in range(N):
                if not k in x:
                    rest.append(k)
            for y in itertools.combinations(rest,i-j):
                draft = 0
                x = [candx[k] for k in x]
                y = [candy[k] for k in 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: Runtime Error

Solution code:
n = int(input())
distances = [0]*(n+1)

allcity = []

for _ in range(n):
    x, y, pop = map(int, input().split())
    closest = min(abs(x), abs(y))
    distances[0] += pop*closest
    allcity.append([x, y, pop, closest])

allcity.sort(reverse = True, key = lambda x: x[2])

# print(allcity)
k = 1
while k<n:
    maxcity = allcity[k-1]

    x, y, maxpop, _ = maxcity
    hori, verti = 0, 0

    for i in range(k, len(allcity)):
        cx, cy, cp, closest = allcity[i]
        # print(maxpop, allcity[i])
        # allcity[i][3] = min(closest, abs(x-cx), abs(y-cy))
        hori += cp*(abs(y - cy))
        verti += cp*(abs(x - cx))
    
    # print(maxpop, hori, verti)
    dist = 0
    if hori < verti:
        # print('horizontal line', maxpop)
        for i in range(1, len(allcity)):
            cx, cy, cp, closest = allcity[i]
            allcity[i][3] = min(closest, (abs(y - cy)))
            dist += cp*allcity[i][3]
    elif verti < hori:
        # print('vertical line', maxpop)
        for i in range(1, len(allcity)):
            cx, cy, cp, closest = allcity[i]
            allcity[i][3] = min(closest, (abs(x - cx)))

            dist += cp*allcity[i][3]
    else:
        disth, distv = 0, 0
        for i in range(1, len(allcity)):
            cx, cy, cp, closest = allcity[i]
            # allcity[i][3] = min(closest, (abs(y - cy)))
            disth += cp*min(closest, (abs(y - cy)))

        for i in range(1, len(allcity)):
            cx, cy, cp, closest = allcity[i]
            # allcity[i][3] = min(closest, (abs(x - cx)))
            distv += cp*min(closest, (abs(x - cx)))

        if disth < distv:
            for i in range(1, len(allcity)):
                cx, cy, cp, closest = allcity[i]
                allcity[i][3] = min(closest, (abs(y - cy)))
        else:
            for i in range(1, len(allcity)):
                cx, cy, cp, closest = allcity[i]
                allcity[i][3] = min(closest, (abs(x - cx)))

    distances[k] = min(disth, distv)
    # allcity.sort(reverse = True, key = lambda x: x[2])
    k += 1

for dist in distances:
    print(dist)

Submission status: Runtime Error

Solution code:
from collections import Counter

n=int(input())
xl=[]
yl=[]
pl=[]
pre=0
for _ in range(n):
  xx,yy,pp=map(int,input().split())
  xl.append(xx)
  yl.append(yy)
  pl.append(pp)
  if xx>=yy:pre+=pp*yy
  else:pre+=pp*xx
print(pre)

ways=[0]*(2*n)
for ix in xl:
  ways.append(pl[ix])

for i in range(1,n):
  for ci_i in range(n):

Submission status: Runtime Error

Solution code:
import numpy as np

def distance(Xline, Yline, XYPs):
    minDs = []
    for XYP in XYPs:
        X, Y, P = XYP[0], XYP[1], XYP[2]
        minX = minY = 10 ** 10
        for Xline_ in Xline:
            minX = min(minX, X-Xline_)
        for Yline_ in Yline:
            minY = min(minY, Y-Yline_)
        minD = min(minX*P, minY*P)
        minDs.append(minD)
    return min(minDs)

# print('input >>')
N = int(input())
XYPs = []

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

XYPs.sort(key=lambda XYP:XYP[2], reverse=True)

Xlines = [0]
Ylines = [0]

for XYP in XYPs:
    X = XYP[0]
    Y = XYP[1]
    print(distance(Xlines, Ylines, XYPs))
    if(distance(Xlines + [X], Ylines, XYPs) < distance(Xlines, Ylines + [Y], XYPs):
        Xlines += [X]
    else:
        Ylines += [Y]

# print('-----output-----')

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class Comb:
    def __init__(self, N):
        F = [1] * (N + 1)
        for i in range(N):
            F[i + 1] = (i + 1) * F[i] % mod

        self.d_inv = {}
        self.d_comb = {}
        self.F = F

    def inv(self, a):
        if a not in self.d_inv:
            self.d_inv[a] = pow(a, mod - 2, mod)
        return self.d_inv[a]

    def comb(self, a, b):
        if (a, b) not in self.d_comb:
            self.d_comb[(a, b)] = (self.F[a] * self.inv(self.F[a - b]) * self.inv(self.F[b])) % mod
            self.d_comb[(a, a - b)] = self.d_comb[(a, b)]
        return self.d_comb[(a, b)] 


def main():
    N = int(input())
    P = read_lists(N)

    CX = [[0 for _ in range(N)] for _ in range(N ** 2)]
    LX = {i: set() for i in range(1, N + 1)}
    C = [0] * (N + 1)

    for T in itertools.product(range(3), repeat=N):
        X = set()
        Y = set()
        for i, t in enumerate(T):
            if t == 1:
                X.add(P[i][0])
            elif t == 2:
                Y.add(P[i][1])

        
        for j, (xp, yp, p) in enumerate(P):
            cx = min(abs(xp - x) for x in X)
            cy = min(abs(yp - y) for y in Y)
            C[len(X) + len(Y)] = min(cx, cy) * p

    
    print(map(str, C))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def hersCode(n, f):
  l = 10001
  r = -10000
  for i in range(N):
    if (1 << i) & n:
      x, y, p = XYP[i]
      if f:
        l = min(l, x)
        r = max(r, x)
      else:
        l = min(l, y)
        r = max(r, y)
  r += 1

  while abs(l - r) > 2:
    d1 = l + (r - l) // 3
    d2 = r - (r - l) // 3
    dd1 = exe(n, f, d1)
    dd2 = exe(n, f, d2)
    if dd1 > dd2:
      r = d2
    else:
      l = d1
  ans = 0
  for i in range(l, r):
    ans = max(ans, exe(n, f, i))
  return ans

def exe(n, f, m):
  q = 0
  for i in range(N):
    if (1 << i) & n:
      x, y, p = XYP[i]
      if f == True:
        if min(abs(x), abs(y)) > abs(x - m):
          q += L[i] - abs(x - m) * p
      else:
        if min(abs(x), abs(y)) > abs(y - m):
          q += L[i] - abs(y - m) * p
  return q

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

L = [0] * N
c = 0
t = 0
for x, y, p in XYP:
  t += min(abs(x), abs(y)) * p
  L[c] = min(abs(x), abs(y)) * p
  c += 1

D = [0] * (1 << N)

for i in range(1, 1 << N):
  D[i] = max(hersCode(i, True), hersCode(i, False))

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

for i in range(1 << N):
  DP[1][i] = D[i]

for i in range(2, N):
  for n in range(1, i):
    for j in range(1 << N):
      for k in range(1 << N):
        if ~j & k: continue
        if j == k: continue
        d = j ^ k
        DP[i][j] = max(DP[i][j], DP[n][k] + DP[i - n][d])

for i in range(N):
  print(t - max(DP[i]))
print(0)

Submission status: Runtime Error

Solution code:
from bisect import bisect
from itertools import combinations

def resolve():
    n = int(input())
    points = []
    xx = [0]
    yy = [0]
    for i in range(n):
        x,y,p = map(int, input().split())
        points.append((x,y,p))
        xx.append(x)
        yy.append(y)

    xx = list(set(xx)).sort()
    yy = list(set(yy)).sort()
    inf = float('INF')
    mn = min(len(xx, yy)) - 1
    for i in range(1,n+1):
        ans = inf
        if r >= mn:
            print(0)
            continue
        for tmp in combinations(range(n), i):
            cost = calc(xx, yy, points, tmp)
            if ans > cost:
                ans = cost

        print(ans)


def calc(points, tmp) -> int:
    xx = [0] + [points[i][0] for i in tmp]
    yy = [0] + [points[i][1] for i in tmp]
    xx.sort()
    yy.sort()
    cost = 0
    for x,y,p in points:
        idx = bisect(xx, x)
        xp = abs(xx[idx] - x)
        idx = bisect(yy, y)
        yp = abs(yy[idx] - y)
        cost += min(xp, yp) * p

    return cost

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
n = int(input())
xyp=[list(map(int,input().split())) for i in range(n)]

from itertools import *

xset=set()
yset=set()
for x,y,p in xyp:
    xset.add(x)
    yset.add(y)

lenx=len(xset)
leny=len(yset)

uniqx=list(xset)
uniqy=list(yset)

uniqx.sort()
uniqy.sort()

for i in range(n+1): # draw i line
    if i>=lenx or i>=leny:
        print(0)
        continue

    ans=10**10
    for tate in range(lenx+1):
        yoko = i-tate
        if yoko<0:
            continue

        for tates in combinations(uniqx,tate):
            for yokos in combinations(uniqy,yoko):
                cur = 0
                for x,y,p in xyp:
                    if x in tates or y in yokos:
                        continue
                    else:
                        for tmp in tates:
                            mindis=min(mindis,abs(x-tmp))
                        for tmp in yokos:
                            mindis=min(mindis,abs(y-tmp))
                        cur+=mindis*p

                ans=min(ans,cur)

    print(ans)

Submission status: Runtime Error

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

if n > 15:
    print(re)
    
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) - 1):
    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
"""
ans[-1] = 0
for res in ans:
    print(res)