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

if N == 1:
  x, y, p = XYP[0]
  print(min(abs(x), abs(y)) * p)
  print(0)
  exit()

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: Time Limit Exceeded

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)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
towns = [tuple(map(int, input().split())) for _ in range(n)]

INF = 10 ** 18
ans = [INF] * (n + 1)

for bit in range(1 << n):
    k = bin(bit).count('1')
    i = 0
    t = bit
    selected = []
    while t:
        if t & 1:
            selected.append(towns[i])
        t >>= 1
        i += 1

    for bit2 in range(1 << k):
        cost = 0
        for x, y, p in towns:
            town_dist = min(abs(x), abs(y))
            t = bit2
            for i in range(k):
                if t & 1:
                    town_dist = min(town_dist, abs(selected[i][1] - y))
                else:
                    town_dist = min(town_dist, abs(selected[i][0] - x))
                t >>= 1
            cost += town_dist * p
        kk = len(selected)
        ans[kk] = min(ans[kk], cost)

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

Submission status: Time Limit Exceeded

Solution code:
def popcnt(n):
    c = (n & 0x5555) + ((n>>1) & 0x5555)
    c = (c & 0x3333) + ((c>>2) & 0x3333)
    c = (c & 0x0f0f) + ((c>>4) & 0x0f0f)
    c = (c & 0x00ff) + ((c>>8) & 0x00ff)
    return c

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

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

for i, x in enumerate(X):
    for k in range(1 << N):
        d = abs(x)
        for j, xx in enumerate(X):
            if k & (1 << j):
                d = min(d, abs(xx - x))
        DX[i][k] = d * P[i]
for i, y in enumerate(Y):
    for k in range(1 << N):
        d = abs(y)
        for j, yy in enumerate(Y):
            if k & (1 << j):
                d = min(d, abs(yy - y))
        DY[i][k] = d * P[i]

ANS = [1 << 100] * (N + 1)

for i in range(1 << N):
    m = i ^ ((1 << N) - 1)
    j = m
    while 1:
        ans = 0
        for k in range(N):
            ans += min(DX[k][i], DY[k][j])
        
        pc = popcnt(i) + popcnt(j)
        ANS[pc] = min(ANS[pc], ans)
        
        if not j:
            break
        j = m & (j - 1)

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

Submission status: Time Limit Exceeded

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

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

ans = [float('inf')] * (n+1)
did = set()
for choice in product([0, 1, 2], repeat=n):
    NS = set()
    WE = set()
    for i, c in enumerate(choice):
        if c == 0:
            # 選ばない
            continue
        elif c == 1:
            # 南北に引く
            NS.add(Y[i])
        else:
            # 東西に引く
            WE.add(X[i])
    NS = tuple(NS)
    WE = tuple(WE)
    if (NS, WE) in did:
        continue
    did.add((NS, WE))
    line = len(NS)+len(WE)
    temp = 0
    for i in range(n):
        vmin = abs(X[i] * P[i])
        for v in WE:
            vmin = min(vmin, abs(X[i]-v)*P[i])
        hmin = abs(Y[i] * P[i])
        for h in NS:
            hmin = min(hmin, abs(Y[i]-h)*P[i])
        temp += min(hmin, vmin)
    ans[line] = min(ans[line], temp)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
from collections import Counter

def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

popcount = [popcount(i) for i in range(1341398)]

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

INF = 10**18+3
EWx = dict()
EWx[0] = 0
SNy = dict()
SNy[0] = 0
geta = 32768

tablee = [[INF]*(popcount[S]+1) for S in range(1<<N)]
tablee[0] = [0]
tables = [[INF]*(popcount[S]+1) for S in range(1<<N)]
tables[0] = [0]

TTx = [[INF]*(1<<N) for _ in range(N)]
TTy = [[INF]*(1<<N) for _ in range(N)]


for i in range(N):
    x, y, p = XYP[i]
    TTx[i][0] = p*abs(x)
    TTy[i][0] = p*abs(y)
    for S in range(1, 1<<N):
        TTx[i][S] = min(TTx[i][(-S&S)^S], p*abs(x-XYP[(-S&S).bit_length()-1][0]))
        TTy[i][S] = min(TTy[i][(-S&S)^S], p*abs(y-XYP[(-S&S).bit_length()-1][1]))

for S in range(1, 1<<N):
    ps = popcount[S]
    T = S
    EWx[S*geta + T] = 0
    SNy[S*geta + T] = 0
    for _ in range((1<<ps)-1):
        T = S&(T-1)
        pt = popcount[T]
        U = S^T
        G = -U&U
        resx = TTx[G.bit_length()-1][T] + EWx[(S^G)*geta+T]
        resy = TTy[G.bit_length()-1][T] + SNy[(S^G)*geta+T]
        EWx[S*geta+T] = resx
        SNy[S*geta+T] = resy
        
        tablee[S][pt] = min(tablee[S][pt], resx)
        tables[S][pt] = min(tables[S][pt], resy)


Ans = [INF]*(N+1)
Ans[-1] = 0
M = (1<<N)-1
for S in range(1<<N):
    ps = popcount[S]
    R = M^S
    for i in range(ps+1):
        for j in range((N-ps)+1):
            Ans[i+j] = min(Ans[i+j], tablee[S][i] + tables[R][j])

print('\n'.join(map(str, Ans)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
XYP = [[int(x) for x in input().split()] for _ in range(N)]

a0 = 0
for i in range(N):
    a0 += min(abs(XYP[i][0]), abs(XYP[i][1])) * XYP[i][2]

ans = [a0] * (N+1)

for i in range(3**N):
    tmp = i
    X = [0]
    Y = [0]
    c = 0
    for j in range(N):
        if(tmp % 3 == 1):
            X.append(XYP[j][0])
            c += 1
        elif(tmp %3 == 2):
            Y.append(XYP[j][1])
            c += 1
        tmp //= 3
    
    a = 0
    for j in range(N):
        dx = min([abs(x - XYP[j][0]) for x in X])
        dy = min([abs(y - XYP[j][1]) for y in Y])
        a += XYP[j][2] * min(dx,dy)
    
    if(ans[c] > a):
        ans[c] = a

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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))
        # print(ans)
    return "\n".join(ans)


#
# import random
#
# N = 5
# for i in range(10000):
#     data = [(random.randint(-3, 3), random.randint(-3, 3), random.randint(1, 10)) for i in range(N)]
#     expected = solve(N, data, True)
#     actual = solve(N, data, False)
#     if expected != actual:
#         print("NG!!!")
#         print(f"expected : {expected}, actual : {actual}")
#         print(data)
#         exit(1)

# solve(3, [(2, 1, 10), (-3, 2, 1), (3, -2, 9)], True)
# solve(3, [(2, 1, 10), (-3, 2, 1), (3, -2, 9)], False)
# exit(0)
#
# 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, True))

Submission status: Time Limit Exceeded

Solution code:
def main():
    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)

    yokomi = [[10**9]*(1<<n) for i in range(n)]
    tatemi = [[10**9]*(1<<n) for i in range(n)]


    for i in range(1<<n):
        yoko = [10000]
        tate = [10000]
        for j in range(n):
            if (i>>j)&1 == 1:
                yoko.append(y[j])
                tate.append(x[j])
        for j in range(n):
            pp = 10**9
            qq = 10**9
            for e in yoko:
                if pp > abs(e-y[j]):
                    pp = abs(e-y[j])
            for e in tate:
                if qq > abs(e-x[j]):
                    qq = min(qq,abs(e-x[j]))
            yokomi[j][i] = pp
            tatemi[j][i] = qq

    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])
        
        xn = 0
        yn = 0
        for i in range(n):
            if idxs[i] == 1:
                yoko.add(y[i])
                yn += 1<<i
            elif idxs[i] == 2:
                tate.add(x[i])
                xn += 1<<i

        tmp = 0
        for i in range(n):
            if idxs[i] == 0:
                mi = min(tatemi[i][xn],yokomi[i][yn])
                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)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
xyp = []
for i in range(N):
    xyp.append(LI())
# xyp = sorted(xyp, key=lambda xyp: xyp[2], reverse= True)
def cal_work(x_lines, y_lines):
    work = 0
    for i in range(N):
        min_dis = mod
        x, y, p = xyp[i]
        for x_line in x_lines:
            min_dis = min(min_dis, abs(x_line - x))
            if min_dis == 0:
                break
        for y_line in y_lines:
            min_dis = min(min_dis, abs(y_line - y))
            if min_dis == 0:
                break
        work += min_dis * p
    return work

def n2kdigit(n,k):
    digits = [0 for i in range(N)]
    cnt = 0
    while n > 0:
        digits[cnt]= n % k
        n = n // k
        cnt += 1
    return digits

anss = [float("inf") for i in range(N + 1)]
for i in range(3 ** N):
    digits = n2kdigit(i, 3)
    x_lines = [0]
    y_lines = [0]
    for i, digit in enumerate(digits):
        if digit == 0:
            pass
        elif digit == 1:
            x_lines.append(xyp[i][0])
        else:
            y_lines.append(xyp[i][1])

    cnt = len(x_lines) + len(y_lines) - 2
    anss[cnt] = min(anss[cnt], cal_work(x_lines, y_lines))

for ans in anss:
    print(ans)

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, max_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 <= 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 = []
    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, [], -1)
        print(S)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(XYP):
    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
    N = len(X)
    dp = np.empty((3**N, N), np.int32)  # 建設、人 -> コスト
    dp[0] = np.minimum(np.abs(X), np.abs(Y))
    size = np.empty(3**N, np.int32)
    size[0] = 0
    for n in range(N):
        B = 3**n
        DX = np.abs(X - X[n])
        DY = np.abs(Y - Y[n])
        dp[B:2 * B] = np.minimum(dp[:B], DX)
        dp[2 * B:3 * B] = np.minimum(dp[:B], DY)
        size[B:2 * B] = size[:B] + 1
        size[2 * B:3 * B] = size[:B] + 1
    ans = np.full(N + 1, 10**18, np.int64)
    for s in range(3**N):
        n = size[s]
        ans[n] = min(ans[n], (P * dp[s]).sum())
    return ans

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i8[:], ))
    cc.compile()

from my_module import main

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:
#E
import sys
input = sys.stdin.readline
def main():
    N=int(input())
    XYP=[None]*N
    for i in range(N):
        XYP[i] = list(map(int,input().split()))
    import itertools
    for k in range(0,N+1):
        ans=10**20
        for q in itertools.combinations(range(N), k):
            #print(q)
            for j in range(2**len(q)):
                bi = bin(j)[2:].zfill(len(q))
                r = [q[i] for i in range(len(q)) if bi[i]=="1"]
                #print(r)
                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[2]*min([ abs(xyp[0]-x) for x in X_trains]+
                           [abs(xyp[1]-y) for y in Y_trains] ) for xyp in XYP )
                ans=min(ans,cost)
        print(ans)
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)
                xs=[0]
                ys=[0]
                for k in range(i):
                    
                    if (j>>k)&1:
                        ys.append(S[t[k]][1])
                        # for li in sea:
                        #     l[li]=min(l[li],abs(S[li][1]-S[t[k]][1])*S[li][2])
                    else:
                        xs.append(S[t[k]][0])
                        # for li in sea:
                        #     l[li]=min(l[li],abs(S[li][0]-S[t[k]][0])*S[li][2])
                xs.sort()
                ys.sort()
                tot=0
                for li in sea:
                    a=inf
                    x,y,s=S[li]
                    xi=bisect_left(xs,x)
                    yi=bisect_left(ys,y)
                    if xi>0:
                        a=min(a,abs(x-xs[xi-1]))
                    if yi>0:
                        a=min(a,abs(y-ys[yi-1]))
                    if xi<len(xs):
                        a=min(a,abs(x-xs[xi]))
                    if yi<len(ys):
                        a=min(a,abs(y-ys[yi]))

                    tot+=a*s


      

               
                ans=min(ans,tot)
        print(ans)
                
                
    




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import copy
INF = float('inf')
N = int(input())
X = []
Y = []
P = []
for _ in range(N):
    x, y, p = list(map(int, input().split()))
    X.append(x)
    Y.append(y)
    P.append(p)

# x = i のライン
x_lines = [0]
# y = j のライン
y_lines = [0]


def cost(x_lines_tmp, y_linens_tmp):
    cost_sum = 0
    for i in range(N):
        min_x = INF
        for x_line in x_lines_tmp:
            min_x = min(min_x, abs(X[i] - x_line))
        min_y = INF
        for y_line in y_linens_tmp:
            min_y = min(min_y, abs(Y[i] - y_line))
        cost_sum += P[i] * min(min_x, min_y)
        # print(P[i] * min(min_x, min_y))
    return cost_sum


l = [(i, 'x') for i in range(N)] + [(i, 'y') for i in range(N)]

for n in range(N+1):
    c_list = list(itertools.combinations(l, n))

    cost_sum = cost(x_lines, y_lines)
    for c in c_list:
        tmp_x_lines = copy.copy(x_lines)
        tmp_y_lines = copy.copy(y_lines)
        for e in c:
            target_index = e[0]
            x_y = e[1]
            if x_y == 'x':
                tmp_x_lines += [X[target_index]]
            else:
                tmp_y_lines += [Y[target_index]]
        cost_sum = min(cost_sum, cost(tmp_x_lines, tmp_y_lines))
        # print(c, tmp_x_lines, tmp_y_lines, cost_sum)
    print(cost_sum)