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

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

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 <= N /2:
    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)
    # else:
    #     break

Submission status: Runtime Error

Solution code:
from itertools import combinations
from bisect import bisect_left

INF = float('INF')
N = int(input())
points = []
scores = []

for i in range(N):
    point = list(map(int,input().split()))
    points.append(point + [i])
    scores.append(max(abs(point[0]), abs(point[1])) * point[2])

for i in range(N+1):
    MIN = INF
    for j in range(i+1):
        for P in combinations(points, N-j):
            X = [0]
            tmp_scores = scores[:]
            for p in points:
                if not p in P:
                    X.append(p[0])
                    tmp_scores[p[3]] = 0
            X.sort()
            X += [100000]
            for p in P:
                index = bisect_left(X, p[0])
                tmp_scores[p[3]] = min(tmp_scores[p[3]], min(p[0]-X[index], X[index+1]-p[0]) * p[2])
            for Q in combinations(P, i-j):
                Y = [0]
                for p in points:
                    if p in Q:
                        Y.append(p[1])
                        tmp_scores[p[3]] = 0
                Y.sort()
                Y += [100000]
                for p in Q:
                    index = bisect_left(Y, p[0])
                    tmp_scores[p[3]] = min(tmp_scores[p[3]], min(p[1]-Y[index], Y[index+1]-p[1]) * p[2])
                MIN = min(MIN, sum(tmp_scores))

print(MIN)

Submission status: Runtime Error

Solution code:
n = int(input())
xyp = [list(map(int,input().split())) for i in range (n) ]
s = [0 for i in range (n)]
for i in range (n):
    s[i] = min(abs(xyp[i][0]*xyp[i][2]),abs(xyp[i][1]*xyp[i][2]))
print(sum(s))
cnt = 0
while True:
    if cnt == n:
        break
    num = s.index(max(s))
    x = xyp[num][0]
    y = xyp[num][1]
    xs = s.copy()
    ys = s.copy()
    for i in range (n):
        xs[i] = min(min(abs(xyp[i][0]),abs(xyp[i][0]-x))*xyp[i][2],abs(xyp[i][1]*xyp[i][2]),xs[i])
    for i in range (n):
        ys[i] = min(abs(xyp[i][0]*xyp[i][2]),min(abs(xyp[i][1]),abs(xyp[i][1]-y))*xyp[i][2],ys[i])
    if sum(xs) <= sum(ys):
        print(sum(xs))
        s = xs
        cnt += 1
    elif  sum(xs) > sum(ys):
        print(sum(ys))
        s = xy
        cnt += 1

Submission status: Runtime Error

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(len(x) + 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: Runtime Error

Solution code:
n, *XYP = map(int, open(0).read().split())
X = list(set(XYP[::3]))
Y = list(set(XYP[1::3]))
mx = len(X)
my = len(Y)
m = len(X) + len(Y)
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))
A = {}
B = {}
for i in range(2**m):
    Lx = [0]
    Ly = [0]
    c = bin(i).count('1')
    for j in range(m):
        if (i>>j) & 1:
            if j < mx:
                Lx.append(X[j])
            else:
                Ly.append(Y[j-mx])
    s = 0
    for x, y, p in XYP:
        d_x = min(abs(x-xl) for xl in Lx)
        d_y = min(abs(y-yl) for yl in Ly)
        s += min(d_x, d_y) * p
    if c in A:
        if A[c] > s:
            A[c] = s
            B[c] = (Lx, Ly)
    else:
        A[c] = s
        B[c] = (Lx, Ly)

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

Submission status: Runtime Error

Solution code:
n = int(input())
x = []
y = []
s = []
p = []

for i in range(n):
    xi, yi, pi = [int(i) for i in input().split()]
    x.append(xi)
    y.append(yi)
    s.append(min(abs(xi), abs(yi)) * pi)
    p.append(pi)

miner = sum(s)
print(miner)

xline = [0]
yline = [0]

for times in range(n):
    minerx = miner
    minery = miner
    for i in range(n):
        if x[i] not in xline:
            tempxline = xline[:] + [x[i]]
            val = 0
            for j in range(n):
                val += min(abs(x[j] - min(tempxline, key=lambda k:abs(k-x[j]))),abs(min(yline, key=lambda k:abs(k-y[j])) - y[j])) * p[j]
            if val < minerx:
                minerx = val
                curxline = tempxline[:]
                

    for i in range(n):
        if y[i] not in yline:
            tempyline = yline[:] + [y[i]]
            val = 0
            for j in range(n):
                val += min(abs(min(tempyline, key=lambda k:abs(k-y[j])) - y[j]), abs(min(xline, key=lambda k:abs(k-x[j])) - x[j])) * p[j]
            if val < minery:
                minery = val
                curyline = tempyline[:]

    if minerx < minery:
        miner = minerx
        xline = curxline
    else:
        miner = minery
        yline = curyline

    print(miner)

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)

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))
    minDistance = [-1] * N
    for j in range(N):
        minDistance = 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:
                minDistance = abs(Resident[j][0] - Resident[k][0])
            if railRoad[k] == 2 and abs(Resident[j][1] - Resident[k][1]) < minDistance:
                minDistance = abs(Resident[j][1] - Resident[k][1])
    cost = 0
    for j in range(N):
        cost += Resident[j][2] + minDistance[j]
    if minCost[numNewRailroad] == -1 or minCost[numNewRailroad] > cost:
        minCost[numNewRailroad] = cost
print('\n'.join(list(map(str,minCost))))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

vector<int> x, y, p;
int p3[16];

int main() {
    p3[0] = 1;
    for (int i = 1; i < 16; i++) p3[i] = p3[i - 1] * 3;

    int n;
    while (scanf("%d", &n) == 1) {
        x.assign(n, 0);
        y.assign(n, 0);
        p.assign(n, 0);

        for (int i = 0; i < n; i++) scanf("%d %d %d", &x[i], &y[i], &p[i]);

        vector<int> lr(n), du(n);
        for (int i = 0; i < n; i++) lr[i] = i, du[i] = i;
        sort(lr.begin(), lr.end(), [](const int &i, const int &j) -> bool { return x[i] == x[j] ? y[i] < y[j] : x[i] < x[j]; });
        sort(du.begin(), du.end(), [](const int &i, const int &j) -> bool { return y[i] == y[j] ? x[i] < x[j] : y[i] < y[j]; });

        vector<long long> res(n + 1, 1e18);
        vector<int> _closest(n);
        for (int i = 0; i < n; i++) _closest[i] = min(abs(x[i]), abs(y[i]));
        for (int m = 0; m < p3[n]; m++) {
            vector<int> vm;
            int tm = m;
            for (int i = 0; i < n; i++) {
                vm.push_back(tm % 3);
                tm /= 3;
            }

            int nonZero = 0;
            for (auto &x : vm) nonZero += x != 0;

            vector<int> closest = _closest;
            int l = -1e9;
            for (int i = 0; i < n; i++)  {
                int id = lr[i];
                if (vm[id] == 1) l = x[id];
                closest[id] = min(x[id] - l, closest[id]);
            }

            int d = -1e9;
            for (int i = 0; i < n; i++)  {
                int id = du[i];
                if (vm[id] == 2) d = y[id];
                closest[id] = min(y[id] - d, closest[id]);
            }

            int r = 1e9;
            for (int i = n - 1; i >= 0; i--)  {
                int id = lr[i];
                if (vm[id] == 1) r = x[id];
                closest[id] = min(r - x[id], closest[id]);
            }

            int u = 1e9;
            for (int i = n - 1; i >= 0; i--)  {
                int id = du[i];
                if (vm[id] == 2) u = y[id];
                closest[id] = min(u - y[id], closest[id]);
            }

            long long tres = 0;
            for (int i = 0; i < n; i++) tres += 1ll * closest[i] * p[i];
            res[nonZero] = min(res[nonZero], tres);
        }

        for (auto &x : res) printf("%lld\n", x);
    }
}

Submission status: Runtime Error

Solution code:
def population(n):
    if n == 0:
        return 0
    if n % 2 == 0:
        return population(n // 2)
    return 1 + population(n // 2)

N = int(input())
X = [0] * N
Y = [0] * N
P = [0] * N
for i in range(N):
    X[i], Y[i], P[i] = map(int, input().split())

ans = [10**10] * (N + 1)

cost = 0
for j in range(N):
    cost2 = min(abs(X[j]), abs(Y[j]))
    cost += cost2 * P[j]
ans[0] = cost
opt = 0

for K in range(1, N + 1):
    for b in range(2 * N):
        i = opt | (1 << b)
        cost = 0
        for j in range(N):
            if i & (1 << j) or i & (1 << (j + N)):
                continue
            cost2 = min(abs(X[j]), abs(Y[j]))
            for l in range(2 * N):
                if (i & (1 << l)) == 0:
                    #print('cont', i)
                    continue
                if l < N:
                    #print('x')
                    cost2 = min(cost2, abs(X[l] - X[j]))
                else:
                    #print('y')
                    cost2 = min(cost2, abs(Y[l - N] - Y[j]))
            cost += cost2 * P[j]
        if ans[K] > cost:
            print(K, i, cost)
            ans[K] = cost
            next_opt = i
    opt = next_opt
for i in range(N + 1):
    print(ans[i])

Submission status: Runtime Error

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)
line[-1] = 0
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-2:
        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-1)
for i in line:
    print(i)

Submission status: Runtime Error

Solution code:
#E
N=int(input())
XYP=[None]*N
for i in range(N):
    XYP[i] = list(map(int,input().split()))

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

Solution code:
import sys
import numpy as np
import itertools


def Ss():
  return sys.stdin.readline().rstrip().split(' ')
 
def Is():
  ss = Ss()
  return map(int, ss) if len(ss) > 1 else int(ss[0])

def eval_pop(pop, xs, ys):
  d = 10000000000
  for x in xs:
    d = min(abs(pop['x'] - x), d)
  for y in ys:
    d = min(abs(pop['y'] - y), d)
  
  return d * pop['p']
    
def eval_pops(pops, xs, ys):
  return np.sum([eval_pop(pop, xs, ys) for pop in pops])

n = Is()
input_pops = []
for i in range(n):
  x, y, pop = Is()
  input_pops.append({'x': x, 'y': y, 'p': pop})

for k in range(n+1):
  pops = sorted(pops, key=lambda pop: pop['p'], reverse=True)
  xs = [0]
  ys = [0]
  
  booms = [[k['x'], k['y']] for p in pops[:k]]
  for element in itertools.product(*booms):
    print(element)
    
  print(eval_pops(pops, xs, ys))

print(pops)

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):
    total_cost = maxcost
    selected_line = ""
    for lines in itertools.combinations(candidate, 1):
        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]
    return total_cost, selected_line

def solve(N, XYPs):
    # 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 = []
    for x in list(Xs):
        candidate.append(("X", x))
    for y in list(Ys):
        candidate.append(("Y", y))

    for k in range(1, N + 1):
        if k >= len(Xs) or k >= len(Ys):
            ans.append("0")
        else:
            cost, selected = t_solve(maxcost, XYPs, candidate, current_lines)
            current_lines.append(selected)
            ans.append(str(cost))
        # print(ans)
    return "\n".join(ans)
#
# import random
#
# for i in range(10):
#     solve(15, [(random.randint(-10, 10),random.randint(-100, 10),random.randint(1, 100)) for i in range(15)])
#
# print("DONE")
#
# assert (solve(3, [(1, 2, 300), (3, 3, 600), (1, 4, 800)]) == "\n".join(
#     ["2900",
#      "900",
#      "0",
#      "0",
#      ]))
# assert (solve(5, [(3, 5, 400), (5, 3, 700), (5, 5, 1000), (5, 7, 700), (7, 5, 400)]) == "\n".join(
#     ["13800",
#      "1600",
#      "0",
#      "0",
#      "0",
#      "0"
#      ]
# ))
# assert (solve(6, [(2, 5, 1000), (5, 2, 1100), (5, 5, 1700), (-2, -5, 900), (-5, -2, 600), (-5, -5, 2200)]) == "\n".join(
#     [
#         "26700",
#         "13900",
#         "3200",
#         "1200",
#         "0",
#         "0",
#         "0"
#     ]))
# assert (solve(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)]) == "\n".join(["2576709",
#                                                                    "1569381",
#                                                                    "868031",
#                                                                    "605676",
#                                                                    "366338",
#                                                                    "141903",
#                                                                    "0",
#                                                                    "0",
#                                                                    "0"
#                                                                    ]))
# print("OK")

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

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


for f in range(2**n):
    kou = set()
    for i in range(n):
        if (f>>i)&1 == 1:
            kou.add(i)
    num = len(kou)

    for rr in range(1<<num):
        yoko = set([10000])
        tate = set([10000])

        for i in range(num):
            if (rr>>i)&1 == 1:
                yoko.add(y[kou[i]])
            else:
                tate.add(x[kou[i]])

        tmp = 0
        for i in range(n):
            if i in kou:
                continue
            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 residx < n+1 and res[residx] > tmp:
            res[residx] = tmp
for e in res:
    print(e)

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define PRIM 3
#define INF (1 << 29)
#define LINF (1LL << 60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;

Int n;
Int x[15], y[15], p[15];
vector<Int> ans(15, LINF);

vector<Int> xs;
vector<Int> ys;
vector<int> no_train;

int main()
{
    cin >> n;
    Int pow3 = 1;
    for (int i = 0; i < n; i++) {
        pow3 *= 3;
        cin >> x[i] >> y[i] >> p[i];
    }
    for (Int i = 0; i < pow3; i++) {
        xs.clear();
        ys.clear();
        no_train.clear();
        int info = i;
        for (int j = 0; j < n; j++) {
            if (info % 3 == 0)
                no_train.push_back(j);
            if (info % 3 == 1)
                xs.push_back(x[j]);
            if (info % 3 == 2)
                ys.push_back(y[j]);
            info /= 3;
        }
        Int dist_sum = 0;
        for (auto j : no_train) {
            Int dist = min(abs(x[j]), abs(y[j]));
            for (auto x_val : xs) {
                dist = min(dist, abs(x_val - x[j]));
            }
            for (auto y_val : ys) {
                dist = min(dist, abs(y_val - y[j]));
            }
            dist_sum += dist * p[j];
        }
        ans[xs.size() + ys.size()] = min(ans[xs.size() + ys.size()], dist_sum);
    }
    for (int i = 0; i <= n; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}