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())
T = [tuple(map(int, input().split())) for _ in range(N)]

INF = 10 ** 6
# INF = float('inf')
dx = [INF] * N
dy = [INF] * N
for i in range(N):
    dx[i] = min(dx[i], abs(T[i][0]))
    dy[i] = min(dy[i], abs(T[i][1]))
tate = [dx * 1 for _ in range(1 << N)]
yoko = [dy * 1 for _ in range(1 << N)]

for bit in product(range(2), repeat=N):
    b = 0
    for i in range(N):
        b += bit[i] * pow(2, (N - 1) - i)
    dx = tate[b]
    dy = yoko[b]
    for i in range(N):
        for j in range(N):
            if bit[i]:
                dx[i] = 0
                dx[j] = min(dx[j], abs(T[i][0] - T[j][0]))
                dy[i] = 0
                dy[j] = min(dy[j], abs(T[i][1] - T[j][1]))

S = [float('inf')] * (N + 1)
for b in range(pow(3, N)):
    k = 0
    x = 0
    y = 0
    i = 0
    while b > 0:
        nb, c = divmod(b, 3)
        if c == 1:
            x += pow(2, (N - 1) - i)
            k += 1
        elif c == 2:
            y += pow(2, (N - 1) - i)
            k += 1
        b = nb
        i += 1
    s = 0
    dx = tate[x]
    dy = yoko[y]
    for i in range(N):
        s += min(dx[i], dy[i]) * T[i][2]
    S[k] = min(S[k], s)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product


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

INF = 10 ** 6
# INF = float('inf')
dx = [INF] * N
dy = [INF] * N
for i in range(N):
    dx[i] = min(dx[i], abs(T[i][0]))
    dy[i] = min(dy[i], abs(T[i][1]))
tate = [dx * 1 for _ in range(1 << N)]
yoko = [dy * 1 for _ in range(1 << N)]

for bit in product(range(2), repeat=N):
    b = 0
    for i in range(N):
        b += bit[i] * pow(2, (N - 1) - i)
    dx = tate[b]
    dy = yoko[b]
    for i in range(N):
        for j in range(N):
            if bit[i]:
                dx[i] = 0
                dx[j] = min(dx[j], abs(T[i][0] - T[j][0]))
                dy[i] = 0
                dy[j] = min(dy[j], abs(T[i][1] - T[j][1]))

S = [float('inf')] * (N + 1)
for bit in product(range(3), repeat=N):
    k = 0
    x = 0
    y = 0
    for i, b in enumerate(bit):
        if b == 1:
            x += pow(2, (N - 1) - i)
            k += 1
        elif b == 2:
            y += pow(2, (N - 1) - i)
            k += 1
    s = 0
    dx = tate[x]
    dy = yoko[y]
    for i in range(N):
        s += min(dx[i], dy[i]) * T[i][2]
    S[k] = min(S[k], s)

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

Submission status: Time Limit Exceeded

Solution code:
import itertools


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

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)

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 or i >= set_cnt:
        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 sl[j] != 0:
                            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 sl[j] != 0:
                            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:
#!/usr/bin/env python3
import sys
rl = sys.stdin.buffer.readline
INF = sys.maxsize

N = int(rl())
PS = [tuple(map(int, rl().split())) for i in range(N)]

def bitcount(n):
  n = n - ((n >> 1) & 0x5555555555555555)
  n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
  n = (n + (n >> 4)) & 0x0f0f0f0f0f0f0f0f
  n = n + (n >> 8)
  n = n + (n >> 16)
  n = n + (n >> 32)
  return n & 0x0000007f

def subsets(s):
  t = s
  while t >= 0:
    t &= s
    yield t
    t -= 1

# (x|y)cost[i][j] := 頂点の集合 i に路線が引かれているとき、j 番目の集落から路線までの最小距離
xcost = [[INF] * N for _ in range(1 << N)]
ycost = [[INF] * N for _ in range(1 << N)]
for i in range(1 << N):
  for j in range(N):
    xcost[i][j] = abs(PS[j][0])
    ycost[i][j] = abs(PS[j][1])
    for k in range(N):
      if ((i >> k) & 1) == 1:
        xcost[i][j] = min(xcost[i][j], abs(PS[j][0] - PS[k][0]))
        ycost[i][j] = min(ycost[i][j], abs(PS[j][1] - PS[k][1]))

# 計算結果の距離を歩行距離(= 距離 * 人口)にする
for i in range(1 << N):
  for j in range(N):
    xcost[i][j] = xcost[i][j] * PS[j][2]
    ycost[i][j] = ycost[i][j] * PS[j][2]

# x, y 座標に引かれた線路の引き方の組み合わせの中から最もコストが小さくなるものを求める
ans = [INF] * (N + 1)
for i in range(1 << N):
  size = bitcount(i)
  for j in subsets(i):
    cost = 0
    for k in range(N):
      # i に含まれていない頂点を合計する(i に含まれている頂点の歩行距離は常に０なので)
      if ((i >> k) & 1) == 0:
        cost += min(xcost[j][k], ycost[i-j][k])

    ans[size] = min(ans[size], cost)

# 結果出力
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
rl = sys.stdin.buffer.readline
INF = sys.maxsize

N = int(rl())
PS = [tuple(map(int, rl().split())) for i in range(N)]

def bitcount(n):
  n = n - ((n >> 1) & 0x5555555555555555)
  n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
  n = (n + (n >> 4)) & 0x0f0f0f0f0f0f0f0f
  n = n + (n >> 8)
  n = n + (n >> 16)
  n = n + (n >> 32)
  return n & 0x0000007f

def subsets(s):
  t = s
  while t >= 0:
    t &= s
    yield t
    t -= 1

# (x|y)cost[i][j] := 頂点の集合 i に路線が引かれているとき、j 番目の集落から路線までの最小距離
xcost = defaultdict(lambda: defaultdict(lambda: INF))
ycost = defaultdict(lambda: defaultdict(lambda: INF))
for i in range(1 << N):
  for j in range(N):
    xcost[i][j] = abs(PS[j][0])
    ycost[i][j] = abs(PS[j][1])
    for k in range(N):
      if ((i >> k) & 1) == 1:
        xcost[i][j] = min(xcost[i][j], abs(PS[j][0] - PS[k][0]))
        ycost[i][j] = min(ycost[i][j], abs(PS[j][1] - PS[k][1]))

# 計算結果の距離を歩行距離(= 距離 * 人口)にする
for i in range(1 << N):
  for j in range(N):
    xcost[i][j] = xcost[i][j] * PS[j][2]
    ycost[i][j] = ycost[i][j] * PS[j][2]

# x, y 座標に引かれた線路の引き方の組み合わせの中から最もコストが小さくなるものを求める
ans = [INF] * (N + 1)
for i in range(1 << N):
  size = bitcount(i)
  for j in subsets(i):
    cost = 0
    for k in range(N):
      # i に含まれていない頂点を合計する(i に含まれている頂点の歩行距離は常に０なので)
      if ((i >> k) & 1) == 0:
        cost += min(xcost[j][k], ycost[i-j][k])

    ans[size] = min(ans[size], cost)

# 結果出力
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
# writer解(c++)を写経した．answerのfor文のところ何やってるかさっぱりわかりませんが…
# https://atcoder.jp/contests/m-solutions2020/submissions/15122924
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        a, b, c = (int(i) for i in input().split())
        X.append(a)
        Y.append(b)
        P.append(c)
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    # bit 001001 とかの1が立っている集落に道を作る
    for bit in range(1 << N):
        for i in range(N):
            X_dist[bit][i] = P[i]*abs(X[i])
            Y_dist[bit][i] = P[i]*abs(Y[i])
            for k in range(N):
                if bit & (1 << k):
                    X_dist[bit][i] = \
                        min(X_dist[bit][i], P[i]*abs(X[i] - X[k]))
                    Y_dist[bit][i] = \
                        min(Y_dist[bit][i], P[i]*abs(Y[i] - Y[k]))

    # これはなに？
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        for j in range(i+1)[::-1]:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# writer解(c++)を写経した．answerのfor文のところ何やってるかさっぱりわかりませんが…
# https://atcoder.jp/contests/m-solutions2020/submissions/15122924
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        a, b, c = (int(i) for i in input().split())
        X.append(a)
        Y.append(b)
        P.append(c)
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    # bit 001001 とかの1が立っている集落に道を作る
    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(X[i])
                cur_y.append(Y[i])
        for i in range(N):
            X_dist[bit][i] = P[i]*min(abs(cx - X[i]) for cx in cur_x)
            Y_dist[bit][i] = P[i]*min(abs(cy - Y[i]) for cy in cur_y)

    # これはなに？
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        for j in range(i+1)[::-1]:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# writer解(c++)を写経した．answerのfor文のところ何やってるかさっぱりわかりませんが…
# https://atcoder.jp/contests/m-solutions2020/submissions/15122924
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    # bit 001001 とかの1が立っている集落に道を作る
    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i, (x, y, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    # これはなに？
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        for j in range(i+1)[::-1]:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = 10**13


def main(N, T):
    pow_2 = [pow(2, i) for i in range(N+1)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    for bit in range(1 << N):
        for i in range(N):
            X_dist[bit][i] = T[i][2]*abs(T[i][0])
            Y_dist[bit][i] = T[i][2]*abs(T[i][1])
            for k in range(N):
                if bit & (1 << k):
                    X_dist[bit][i] = \
                        min(X_dist[bit][i], T[i][2]*abs(T[i][0] - T[k][0]))
                    Y_dist[bit][i] = \
                        min(Y_dist[bit][i], T[i][2]*abs(T[i][1] - T[k][1]))

    answer = [INF] * (N+1)
    for bit in range(3**15):
        x_bit = 0
        y_bit = 0
        cnt = 0
        for i in range(N):
            b = bit % 3
            bit //= 3
            if b == 2:
                # x = a
                x_bit += pow_2[i]
                cnt += 1
            elif b == 1:
                # y = a
                y_bit += pow_2[i]
                cnt += 1
        # 距離の評価
        cur_d = 0
        for i in range(N):
            cur_d += min(X_dist[x_bit][i], Y_dist[y_bit][i])
        answer[cnt] = min(answer[cnt], cur_d)

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    main(N, T)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0F0F0F0F0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F0F0F0F0F)
    c = (c & 0x00FF00FF00FF00FF) + ((c >> 8) & 0x00FF00FF00FF00FF)
    c = (c & 0x0000FFFF0000FFFF) + ((c >> 16) & 0x0000FFFF0000FFFF)
    c = (c & 0x00000000FFFFFFFF) + ((c >> 32) & 0x00000000FFFFFFFF)
    return c


n = int(input())
infi = 10 ** 20
kouho = []
for _ in range(n):
    x, y, p = map(int, input().split())
    kouho.append((x, y, p))


num = 1 << n

x_kouho = [[infi] * (n) for _ in range(num)]
y_kouho = [[infi] * (n) for _ in range(num)]
for i in range(num):
    xroad = [0]
    yroad = [0]
    for j in range(n):
        x, y, p = kouho[j]
        if (i >> j) & 1:
            xroad.append(x)
            yroad.append(y)
    for j in range(n):
        x, y, p = kouho[j]
        xtemp = abs(y - 0)
        ytemp = abs(x - 0)
        for a in xroad:
            xtemp = min(xtemp, abs(x - a))
        for b in yroad:
            ytemp = min(ytemp, abs(y - b))
        x_kouho[i][j] = p * xtemp
        y_kouho[i][j] = p * ytemp

ans = [infi] * (n + 1)

for idx in range(num):
    for idx2 in range(num):
        if idx & idx2 != 0:
            continue
        res = 0
        for i in range(n):
            res += min(x_kouho[idx][i], y_kouho[idx2][i])
        cnt = popcnt(idx) + popcnt(idx2)
        ans[cnt] = min(ans[cnt], res)
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
# 解説と 提出 #15122924 を参考に作成.
# 遅い. PyPyで出すと通る. はず.

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, X, Y, P):
    inf = 10 ** 18
    cnb_N = 2 ** N
    # 前計算
    # # 集落の部分集合毎の、Y軸X軸へのそれぞれの最短経路
    to_x = [[0] * N for _ in range(cnb_N)]
    to_y = [[0] * N for _ in range(cnb_N)]
    for cn in range(cnb_N):
        for n in range(N):
            to_x[cn][n] = abs(X[n]) * P[n]
            to_y[cn][n] = abs(Y[n]) * P[n]
            for n2 in range(N):
                if cn >> n2 & 1:
                    to_x[cn][n] = min(to_x[cn][n], abs(X[n] - X[n2]) * P[n])
                    to_y[cn][n] = min(to_y[cn][n], abs(Y[n] - Y[n2]) * P[n])

    # 実計算
    # # 各集落の集合に対して、Y軸を取った場合とX軸を取った場合で最短となる経路を算出
    ans = [inf] * (N + 1)
    for cn in range(cnb_N):
        count = 0
        for i in range(N):
            count += 1 if cn >> i & 1 else 0
        cn2 = cn
        while cn2 >= 0:
            cn2 = cn2 & cn
            subsum = 0
            for n in range(N):
                # if not (cn >> n & 1):
                subsum += min(to_x[cn - cn2][n], to_y[cn2][n])
            ans[count] = min(ans[count], subsum)
            cn2 -= 1

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


if __name__ == '__main__':
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    X, Y, P = [], [], []
    for _ in range(N):
        tmp = [int(i) for i in input().split()]
        X.append(tmp[0])
        Y.append(tmp[1])
        P.append(tmp[2])
    solve(N, X, Y, P)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque

INF = 1 << 50

def generate_dist_arr(X, Y, P):
    N = len(X)
    dist_arr_x = [[] for _ in range(1<<N)]
    dist_arr_y = [[] for _ in range(1<<N)]
    for j in range(1 << N):  # x-y-lines
        x_lines_list = [0]
        y_lines_list = [0]
        for k in range(N):
            if j >> k & 1:
                x_lines_list.append(X[k])
                y_lines_list.append(Y[k])

        dist_xx, dist_yy = [INF] * N, [INF] * N
        x_lines_list = sorted(x_lines_list)
        y_lines_list = sorted(y_lines_list)
        for idx, x in enumerate(X):
            v = bisect.bisect_left(x_lines_list, x)
            pre_x = x_lines_list[min(v-1,  0)]
            post_x = x_lines_list[min(v, len(x_lines_list)-1)]
            dist_xx[idx] = min(abs(pre_x - x), abs(post_x - x)) * P[idx]
        dist_arr_x[j] = dist_xx

        for idx, y in enumerate(Y):
            v = bisect.bisect_left(y_lines_list, y)
            pre_y = y_lines_list[max(v-1, 0)]
            post_y = y_lines_list[min(v, len(y_lines_list) - 1)]
            dist_yy[idx] = min(abs(pre_y - y), abs(post_y - y)) * P[idx]
        dist_arr_y[j] = dist_yy
    return dist_arr_x, dist_arr_y

def calc(val_list):
    val_list = sorted(val_list)
    n = len(val_list)
    dp = [[INF] * (n+1) for _ in range(n+1)]
    dp[0][0] = 0

    for l in range(n+1):
        for r in range(l+1, n+1):
            next_dist = INF
            for k in range(l+1, r+1):
                sum = 0
                for v in range(l+1, r+1):
                    sum += abs(val_list[v-1][0] - val_list[k-1][0]) * val_list[v-1][1]
                next_dist = min(next_dist, sum)
            for j in range(n):
                dp[r][j + 1] = min(dp[r][j + 1], dp[l][j] + next_dist)
            # 0-line
            sum = 0
            for v in range(l + 1, r + 1):
                sum += abs(val_list[v-1][0]) * val_list[v-1][1]
            next_dist = sum

            for j in range(n+1):
                dp[r][j] = min(dp[r][j], dp[l][j]+next_dist)
    return dp


def run():
    N = int(sysread())
    X, Y = [], []

    for i in range(1, N+1):
        x,y,p = map(int, sysread().split())
        X.append((x, p))
        Y.append((y, p))

    ans = [INF] * (N + 1)


    for i in range(1 << N):# x-y-directions
        x_town_list = []
        y_town_list = []
        for k in range(N):
            if i >> k & 1:
                x_town_list.append(X[k])
            else:
                y_town_list.append(Y[k])
        #print('x', x_town_list)
        #print('y', y_town_list)
        dp_x = calc(x_town_list)[-1]
        dp_y = calc(y_town_list)[-1]
        #print(calc(x_town_list))
        #print(calc(y_town_list), '\n')
        #print(bin(i))
        #print(dist_towns_x)
        #print(dist_towns_y)

        for i in range(len(dp_x)):
            for j in range(len(dp_y)):
                val = dp_x[i] + dp_y[j]
                ans[i + j] = min(ans[i + j], val)


    for a in ans:
        print(a)


if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    xyp=[list(map(int,input().split()))for _ in range(n)]
    ans=[10**20]*(n+1)
    ans[0]=sum(min(abs(x),abs(y))*p for x,y,p in xyp)
    ans[-1]=0
    xx=[[]]
    yy=[[]]
    for bitt in range(1,1<<n):
        xs=[(10**20,0)]
        ys=[(10**20,0)]
        for i in range(n):
            if bitt&(1<<i):
                xs.append((xyp[i][0],i))
                ys.append((xyp[i][1],i))
        xs.sort()
        ys.sort()
        xx.append(xs)
        yy.append(ys)
    for trit in range(1,3**n):
        z=0
        xbit=0
        ybit=0
        for i in range(n):
            if trit%3==0:z+=1
            if trit%3==1:xbit+=1<<i
            if trit%3==2:ybit+=1<<i
            trit//=3
        if z==0:continue
        anss=[min(abs(x),abs(y))*p for x,y,p in xyp]
        if xbit:
            xs=xx[xbit]
            i=0
            notx=[1]*n
            for x,j in xx[-xbit-1][:-1]:
                while abs(xs[i][0]-x)>abs(xs[i+1][0]-x):i+=1
                anss[j]=min(anss[j],abs(xs[i][0]-x)*xyp[j][2])
                notx[j]=0
            for j in range(n):
                if notx[j]:anss[j]=0
        if ybit:
            ys=yy[ybit]
            i=0
            noty=[1]*n
            for y,j in yy[-ybit-1][:-1]:
                while abs(ys[i][0]-y)>abs(ys[i+1][0]-y):i+=1
                anss[j]=min(anss[j],abs(ys[i][0]-y)*xyp[j][2])
                noty[j]=0
            for j in range(n):
                if noty[j]:anss[j]=0
        ans[n-z]=min(ans[n-z],sum(anss))
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
xyp=[list(map(int,input().split()))for _ in range(n)]
ans=[10**20]*(n+1)
ans[0]=sum(min(abs(x),abs(y))*p for x,y,p in xyp)
ans[-1]=0
xx=[[]]
yy=[[]]
for bitt in range(1,1<<n):
    xs=[(10**20,0)]
    ys=[(10**20,0)]
    for i in range(n):
        if bitt&(1<<i):
            xs.append((xyp[i][0],i))
            ys.append((xyp[i][1],i))
    xs.sort()
    ys.sort()
    xx.append(xs)
    yy.append(ys)
for trit in range(3**n):
    z=0
    xbit=0
    ybit=0
    for i in range(n):
        if trit%3==0:z+=1
        if trit%3==1:xbit+=1<<i
        if trit%3==2:ybit+=1<<i
        trit//=3
    anss=[min(abs(x),abs(y))*p for x,y,p in xyp]
    if xbit:
        xs=xx[xbit]
        i=0
        notx=[1]*n
        for x,j in xx[-xbit-1][:-1]:
            while abs(xs[i][0]-x)>abs(xs[i+1][0]-x):i+=1
            anss[j]=min(anss[j],abs(xs[i][0]-x)*xyp[j][2])
            notx[j]=0
        for j in range(n):
            if notx[j]:anss[j]=0
    if ybit:
        ys=yy[ybit]
        i=0
        noty=[1]*n
        for y,j in yy[-ybit-1][:-1]:
            while abs(ys[i][0]-y)>abs(ys[i+1][0]-y):i+=1
            anss[j]=min(anss[j],abs(ys[i][0]-y)*xyp[j][2])
            noty[j]=0
        for j in range(n):
            if noty[j]:anss[j]=0
    ans[n-z]=min(ans[n-z],sum(anss))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque


INF = 1 << 50

def generate_dist_arr(X, Y, P):
    N = len(X)
    dist_arr_x = [[] for _ in range(1<<N)]
    dist_arr_y = [[] for _ in range(1<<N)]
    for j in range(1 << N):  # x-y-lines
        x_lines_list = [0]
        y_lines_list = [0]
        for k in range(N):
            if j >> k & 1:
                x_lines_list.append(X[k])
                y_lines_list.append(Y[k])

        dist_xx, dist_yy = [INF] * N, [INF] * N
        x_lines_list = sorted(x_lines_list)
        y_lines_list = sorted(y_lines_list)
        for idx, x in enumerate(X):
            v = bisect.bisect_left(x_lines_list, x)
            pre_x = x_lines_list[min(v-1,  0)]
            post_x = x_lines_list[min(v, len(x_lines_list)-1)]
            dist_xx[idx] = min(abs(pre_x - x), abs(post_x - x)) * P[idx]
        dist_arr_x[j] = dist_xx

        for idx, y in enumerate(Y):
            v = bisect.bisect_left(y_lines_list, y)
            pre_y = y_lines_list[max(v-1, 0)]
            post_y = y_lines_list[min(v, len(y_lines_list) - 1)]
            dist_yy[idx] = min(abs(pre_y - y), abs(post_y - y)) * P[idx]
        dist_arr_y[j] = dist_yy
    return dist_arr_x, dist_arr_y


def run():
    N = int(sysread())
    X, Y, P = [], [], []
    ans = [INF] * N

    for i in range(1, N+1):
        x,y,p = map(int, sysread().split())
        X.append(x)
        Y.append(y)
        P.append(p)

    ans = [INF] * (N + 1)

    dist_arr_x , dist_arr_y = generate_dist_arr(X,Y,P)

    for i in range(1 << N):# x-y-directions
        dist_towns_x = [INF] * (N + 1)
        dist_towns_y = [INF] * (N + 1)
        x_town_list = []
        y_town_list = []
        for k in range(N):
            if i >> k & 1:
                x_town_list.append(k)
            else:
                y_town_list.append(k)


        for j in range(1 << N):  # x-lines
            x_lines_list = [0]
            for k in range(N):
                if j >> k & 1:
                    x_lines_list.append(X[k])

            dists_base = dist_arr_x[j]
            dist_ = []
            for k in x_town_list:
                dist_.append(dists_base[k])

            tmp = len(x_lines_list)-1
            dist_towns_x[tmp] = min(sum(dist_), dist_towns_x[tmp])

        for j in range(1 << N):  # y-lines
            y_lines_list = [0]
            for k in range(N):
                if j >> k & 1:
                    y_lines_list.append(Y[k])

            dists_base = dist_arr_y[j]
            dist_ = []
            for k in y_town_list:
                dist_.append(dists_base[k])

            tmp = len(y_lines_list) - 1
            dist_towns_y[tmp] = min(sum(dist_), dist_towns_y[tmp])

        #print(bin(i))
        #print(dist_towns_x)
        #print(dist_towns_y)

        for i in range(N + 1):
            for j in range(N + 1 - i):
                val = dist_towns_x[i] + dist_towns_y[j]
                ans[i + j] = min(ans[i + j], val)


    for a in ans:
        print(a)


if __name__ == "__main__":
    run()