Problem:


Score: 500 points

Problem Statement

New AtCoder City has an infinite grid of streets, as follows:

At the center of the city stands a clock tower. Let (0, 0) be the coordinates of this point.

A straight street, which we will call East-West Main Street, runs east-west and passes the clock tower. It corresponds to the x-axis in the two-dimensional coordinate plane.

There are also other infinitely many streets parallel to East-West Main Street, with a distance of 1 between them. They correspond to the lines \ldots, y = -2, y = -1, y = 1, y = 2, \ldots in the two-dimensional coordinate plane.

A straight street, which we will call North-South Main Street, runs north-south and passes the clock tower. It corresponds to the y-axis in the two-dimensional coordinate plane.

There are also other infinitely many streets parallel to North-South Main Street, with a distance of 1 between them. They correspond to the lines \ldots, x = -2, x = -1, x = 1, x = 2, \ldots in the two-dimensional coordinate plane.

There are N residential areas in New AtCoder City. The i-th area is located at the intersection with the coordinates (X_i, Y_i) and has a population of P_i. Each citizen in the city lives in one of these areas.

The city currently has only two railroads, stretching infinitely, one along East-West Main Street and the other along North-South Main Street.

M-kun, the mayor, thinks that they are not enough for the commuters, so he decides to choose K streets and build a railroad stretching infinitely along each of those streets.

Let the walking distance of each citizen be the distance from his/her residential area to the nearest railroad.

M-kun wants to build railroads so that the sum of the walking distances of all citizens, S, is minimized.

For each K = 0, 1, 2, \dots, N, what is the minimum possible value of S after building railroads?

Constraints

1 \leq N \leq 15

-10 \ 000 \leq X_i \leq 10 \ 000

-10 \ 000 \leq Y_i \leq 10 \ 000

1 \leq P_i \leq 1 \ 000 \ 000

The locations of the N residential areas, (X_i, Y_i), are all distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1 P_1
X_2 Y_2 P_2
 :  :  :
X_N Y_N P_N

Output

Print the answer in N+1 lines.

The i-th line (i = 1, \ldots, N+1) should contain the minimum possible value of S after building railroads for the case K = i-1.

Sample Input 1

3
1 2 300
3 3 600
1 4 800

Sample Output 1

2900
900
0
0

When K = 0, the residents of Area 1, 2, and 3 have to walk the distances of 1, 3, and 1, respectively, to reach a railroad.

Thus, the sum of the walking distances of all citizens, S, is 1 \times 300 + 3 \times 600 + 1 \times 800 = 2900.

When K = 1, if we build a railroad along the street corresponding to the line y = 4 in the coordinate plane, the walking distances of the citizens of Area 1, 2, and 3 become 1, 1, and 0, respectively.

Then, S = 1 \times 300 + 1 \times 600 + 0 \times 800 = 900.

We have many other options for where we build the railroad, but none of them makes S less than 900.

When K = 2, if we build a railroad along the street corresponding to the lines x = 1 and x = 3 in the coordinate plane, all citizens can reach a railroad with the walking distance of 0, so S = 0. We can also have S = 0 when K = 3.

The figure below shows the optimal way to build railroads for the cases K = 0, 1, 2.

The street painted blue represents the roads along which we build railroads.

Sample Input 2

5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400

Sample Output 2

13800
1600
0
0
0
0

The figure below shows the optimal way to build railroads for the cases K = 1, 2.

Sample Input 3

6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200

Sample Output 3

26700
13900
3200
1200
0
0
0

The figure below shows the optimal way to build railroads for the case K = 3.

Sample Input 4

8
2 2 286017
3 1 262355
2 -2 213815
1 -3 224435
-2 -2 136860
-3 -1 239338
-2 2 217647
-1 3 141903

Sample Output 4

2576709
1569381
868031
605676
366338
141903
0
0
0

The figure below shows the optimal way to build railroads for the case K = 4.



Sample input:
3
1 2 300
3 3 600
1 4 800


Sample output:
2900
900
0
0

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    xc = [[0] * n for _ in range(1 << n)]
    yc = [[0] * n for _ in range(1 << n)]
    for s in range(1 << n):
        for i,(x, y, p) in enumerate(xyp):
            xcost = abs(x)
            ycost = abs(y)
            for j, (lx, ly, _) in enumerate(xyp):
                if s >> j & 1 == 0: continue
                xcost = min(xcost, abs(x - lx))
                ycost = min(ycost, abs(y - ly))
            xc[s][i] = xcost * p
            yc[s][i] = ycost * p

    ans = [inf] * (n + 1)
    for s in range(1 << n):
        k = bin(s).count("1")
        xs = (1 << n) - 1
        while xs > 0:
            xs &= s
            xcs=xc[xs]
            ycs=yc[s-xs]
            ans[k]=min(ans[k], sum(min(xcs[i], ycs[i]) for i in range(n)))
            xs -= 1

    for a in ans: print(a)

inf = 10 ** 16
n = II()
xyp = LLI(n)

solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from itertools import product
    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という道路群を建設したときの，各集落の評価距離
    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 = [100_000_000_000] * (N+1)
    for bit_S in product(range(3), repeat=N):
        x_bit = 0
        y_bit = 0
        x_set = set()
        y_set = set()
        for i in range(N):
            if bit_S[i] == 2:
                # x = a
                x_bit += pow(2, i)
                x_set.add(T[i][0])
            elif bit_S[i] == 1:
                # y = a
                y_bit += pow(2, i)
                y_set.add(T[i][1])
        cnt = len(x_set) + len(y_set)
        # 距離の評価
        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__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from itertools import product
    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という道路群を建設したときの，各集落の評価距離
    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 = [10**18] * (N+1)
    for bit_S in product(range(3), repeat=N):
        x_bit = 0
        y_bit = 0
        x_set = set()
        y_set = set()
        for i in range(N):
            if bit_S[i] == 2:
                # x = a
                x_bit += pow(2, i)
                x_set.add(T[i][0])
            elif bit_S[i] == 1:
                # y = a
                y_bit += pow(2, i)
                y_set.add(T[i][1])
        cnt = len(x_set) + len(y_set)
        # 距離の評価
        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__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    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という道路群を建設したときの，各集落の評価距離
    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)

    def to_3(num):
        s = []
        while num > 0:
            s.append(str(num % 3))
            num //= 3
        return "{:0>15}".format("".join(s[::-1]))

    answer = [10**18] * (N+1)
    for bit in range(pow(3, N)):
        bit_S = to_3(bit)[-N:]
        x_bit = 0
        y_bit = 0
        x_set = set()
        y_set = set()
        for i in range(N):
            if bit_S[i] == "2":
                # x = a
                x_bit += pow(2, i)
                x_set.add(T[i][0])
            elif bit_S[i] == "1":
                # y = a
                y_bit += pow(2, i)
                y_set.add(T[i][1])
        cnt = len(x_set) + len(y_set)
        # 距離の評価
        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__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    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という道路群を建設したときの，各集落の評価距離
    for bit in range(1 << N):
        cur_x = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
        for i, (x, _, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)

    # bitという道路群を建設したときの，各集落の評価距離
    for bit in range(1 << N):
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_y.append(T[i][1])
        for i, (_, y, p) in enumerate(T):
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    def to_3(num):
        s = []
        while num > 0:
            s.append(str(num % 3))
            num //= 3
        return "{:0>15}".format("".join(s[::-1]))

    answer = [10**18] * (N+1)
    for bit in range(pow(3, N)):
        bit_S = to_3(bit)[-N:]
        x_bit = 0
        y_bit = 0
        x_set = set()
        y_set = set()
        for i in range(N):
            if bit_S[i] == "2":
                # x = a
                x_bit += 1 << i
                x_set.add(T[i][0])
            elif bit_S[i] == "1":
                # y = a
                y_bit += 1 << i
                y_set.add(T[i][1])
        cnt = len(x_set) + len(y_set)
        # 距離の評価
        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__':
    main()

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 j in range(1 << N):
    x = j
    while x >= 0:
      x &= j
      d = j ^ x
      DP[i][j] = max(DP[i][j], DP[1][d] + DP[i - 1][x])
      x -= 1

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from bisect import bisect
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    xc = [[0] * n for _ in range(1 << n)]
    yc = [[0] * n for _ in range(1 << n)]
    for s in range(1 << n):
        for i,(x, y, p) in enumerate(xyp):
            xcost = abs(x)
            ycost = abs(y)
            for j, (lx, ly, _) in enumerate(xyp):
                if s >> j & 1 == 0: continue
                xcost = min(xcost, abs(x - lx))
                ycost = min(ycost, abs(y - ly))
            xc[s][i] = xcost * p
            yc[s][i] = ycost * p

    def chmin(i, val):
        if ans[i] > val: ans[i] = val

    ans = [inf] * (n + 1)
    for s in range(1 << n):
        k = bin(s).count("1")
        xs = (1 << n) - 1
        while xs > 0:
            xs &= s
            chmin(k, sum(min(xc[xs][i], yc[s - xs][i]) for i in range(n)))
            xs -= 1

    for a in ans: print(a)

inf = 10 ** 16
n = II()
xyp = LLI(n)

solve()

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):
      x = j
      while x >= 0:
        x &= j
        d = j ^ x
        DP[i][j] = max(DP[i][j], DP[n][x] + DP[i - n][d])
        x -= 1

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
X = []
Y = []
P = []
for _ in range(N):
    x,y,p = map(int,readline().split())
    X.append(x)
    Y.append(y)
    P.append(p)

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

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

PC = [0]*(1<<N)
for i in range(1<<N):
    PC[i] = PC[i//2] + 1 if i % 2 else PC[i//2]

RA = []
for i in range(1<<N):
    t = []
    for j in range(N):
        if i>>j & 1:
            t.append(j)
    RA.append(t)

INF = 10**31
mm = (1 << N) - 1
ANS = [INF]*(N+1)

for i in range(1<<N):
    m = i^mm
    j = m
    dxi = DX[i]
    pci = PC[i]
    while True:
        dyj = DY[j]
        ans = 0
        for k in RA[i^j^mm]:
            ans += min(dxi[k],dyj[k])
        pc = pci + PC[j]
        if ans < ANS[pc]:
            ANS[pc] = ans       
        if j == 0:
            break
        j = m & (j - 1)
print(*ANS,sep = '\n')

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import numpy as np


def f(idx):
    ret = np.zeros((1 << n, n), np.int64)

    for i in range(1 << n):
        lines = [0]
        now = i
        for j in range(n):
            if now & 1:
                lines.append(xyp[j][idx])
            now >>= 1

        for j, (e, p) in enumerate(map(itemgetter(idx, 2), xyp)):
            dist = INF
            for el in lines:
                dist = min(dist, abs(e - el))

            ret[i, j] = dist * p

    return ret


def pow3topow2(pow3):
    v = 0
    h = 0
    cnt = 0
    pow2 = 1
    while pow3:
        pow3, r = divmod(pow3, 3)
        if r == 1:
            v += pow2
            cnt += 1
        elif r == 2:
            h += pow2
            cnt += 1

        pow2 *= 2

    return v, h, cnt


n = int(input())
xyp = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 18

ver = f(0)
hor = f(1)

ans = [INF] * (n + 1)
powers = [pow3topow2(i) for i in range(3 ** n)]
for i in range(3 ** n):
    vi, hi, cnt = powers[i]
    score = np.minimum(ver[vi], hor[hi]).sum()
    ans[cnt] = min(ans[cnt], score)

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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import numpy as np
from numba import njit


def f(idx):
    ret = np.zeros((1 << n, n), np.int64)

    for i in range(1 << n):
        lines = [0]
        now = i
        for j in range(n):
            if now & 1:
                lines.append(xyp[j][idx])
            now >>= 1

        for j, (e, p) in enumerate(map(itemgetter(idx, 2), xyp)):
            dist = INF
            for el in lines:
                dist = min(dist, abs(e - el))

            ret[i, j] = dist * p

    return ret


@njit
def pow3topow2(pow3):
    v = 0
    h = 0
    cnt = 0
    pow2 = 1
    while pow3:
        pow3, r = divmod(pow3, 3)
        if r == 1:
            v += pow2
            cnt += 1
        elif r == 2:
            h += pow2
            cnt += 1

        pow2 *= 2

    return v, h, cnt


n = int(input())
xyp = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 18

ver = f(0)
hor = f(1)

ans = [INF] * (n + 1)
for i in range(3 ** n):
    vi, hi, cnt = pow3topow2(i)

    score = np.minimum(ver[vi], hor[hi]).sum()

    ans[cnt] = min(ans[cnt], score)

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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


def f(idx):
    ret = []
    for i in range(1 << n):
        lines = [0]
        for j in range(n):
            if i & 1:
                lines.append(xyp[j][idx])
            i >>= 1

        costs = []
        for e, p in map(itemgetter(idx, 2), xyp):
            dist = INF
            for el in lines:
                dist = min(dist, abs(e - el))
            costs.append(dist * p)

        ret.append(costs)

    return ret


n = int(input())
xyp = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 18

ver = f(0)
hor = f(1)

ans = [INF] * (n + 1)
for i in range(3 ** n):
    now = i
    vi = 0
    hi = 0
    power = 1
    cnt = n
    for j in range(n):
        q, r = divmod(now, 3)
        if r == 1:
            vi += power
        elif r == 2:
            hi += power
        else:
            cnt -= 1
        now = q
        power *= 2

    score = 0
    for ev, eh in zip(ver[vi], hor[hi]):
        score += min(ev, eh)

    ans[cnt] = min(ans[cnt], score)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n = int(input())
xyp = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 18

ver = dict()
ver[()] = [abs(x) * p for x, _, p in xyp]
for cnt in range(1, n + 1):
    for pat in combinations(range(n), cnt):
        lines = [0]
        for i in pat:
            lines.append(xyp[i][0])

        costs = []
        for x, _, p in xyp:
            dist = INF
            for e in lines:
                dist = min(dist, abs(x - e))
            costs.append(dist * p)

        ver[pat] = costs

hor = dict()
hor[()] = [abs(y) * p for _, y, p in xyp]
for cnt in range(1, n + 1):
    for pat in combinations(range(n), cnt):
        lines = [0]
        for i in pat:
            lines.append(xyp[i][1])

        costs = []
        for _, y, p in xyp:
            dist = INF
            for e in lines:
                dist = min(dist, abs(y - e))
            costs.append(dist * p)

        hor[pat] = costs

ans = [INF] * (n + 1)
for i in range(3 ** n):
    now = i
    v = []
    h = []
    cnt = n
    for j in range(n):
        q, r = divmod(now, 3)
        if r == 1:
            v.append(j)
        elif r == 2:
            h.append(j)
        else:
            cnt -= 1
        now = q

    v = tuple(v)
    h = tuple(h)

    score = 0
    for ev, eh in zip(ver[v], hor[h]):
        score += min(ev, eh)

    ans[cnt] = min(ans[cnt], score)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = [float("INF")]*(n+1)

l = [list(map(int,input().split())) for i in range(n)]

for i in range(3**n):
    now = i
    X = [0]
    Y = [0]
    count = 0
    for j in range(n):
        m = now%3
        if m == 1:
            X.append(l[j][1])
            count += 1
        elif m == 2:
            Y.append(l[j][0])
            count += 1
        now //= 3
    cal = 0
    for x,y,p in l:
        c = float("INF")
        for nx in X:
            c = min(c,abs(y-nx))
        for ny in Y:
            c = min(c,abs(x-ny))
        cal += c*p
    ans[count] = min(ans[count],cal)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[tuple(map(int,input().split()))for i in range(n)]
X,Y,P=zip(*l)
xs,ys,un=[],[],[]
res=[float('inf')]*(n+1)
for i in range(3**n):
    xs.clear()
    ys.clear()
    un.clear()
    for k in range(n):
        if i%3==0:xs.append(k)
        elif i%3==1:ys.append(k)
        else:un.append(k)
        i//=3
    preans=0

    for u in un:
        x=X[u]
        y=Y[u]
        udist=min(abs(x),abs(y))
        for xline in xs:
            udist=min(udist,abs(x-X[xline]))
        for yline in ys:
            udist=min(udist,abs(y-Y[yline]))
        preans+=P[u]*udist

    res[len(xs)+len(ys)]=min(res[len(xs)+len(ys)],preans)
for i in range(n+1):print(res[i])

Submission status: Time Limit Exceeded

Solution code:
from itertools import product,count

def solve(A):
    min2 = lambda x,y: x if x < y else y
    N = len(A)
    vert = [None]*(N * 2**N)
    hori = [None]*(N * 2**N)
    i = 0
    for comb in range(1 << N):
        b = bin(comb|(1 << N))[3:]
        b = [c == "1" for c in b]
        for x,y,p in A:
            mx = abs(x)
            my = abs(y)
            for f,(x2,y2,_) in zip(b,A):
                if f:
                    mx = min2(mx, abs(x-x2))
                    my = min2(my, abs(y-y2))
            vert[i] = mx*p
            hori[i] = my*p
            i += 1

    vert = tuple(vert)
    hori = tuple(hori)

    res = [sum(map(min2,vert[:N],hori[:N]))]*(N+1)
    for i in range(1 << N):
        cnt = bin(i).count('1')
        j = i
        while j >= 0:
            j &= i
            k = i&(~j)
            res[cnt] = min2(res[cnt], sum(map(min2,vert[j*N:(j+1)*N],hori[k*N:(k+1)*N])))
            j -= 1

    return res



if __name__ == '__main__':
    N = int(input())
    A = [tuple(map(int,input().split())) for _ in range(N)]
    print(*solve(A), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

DP1=[20000]*N

S=0
for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))
    S+=DP1[i]*p

ANS[0]=S

def dfs(DP,now,used):
    if used==N-1:
        return
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(tuple(DP2),next_town+1,used+1)

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(tuple(DP2),next_town+1,used+1)

dfs(tuple(DP1),0,0)

for i in range(1,N):
    ANS[i]=min(ANS[i],ANS[i-1])

print(*ANS)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

DP1=[1<<60]*N

for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))*p

ANS[0]=sum(DP1)

def dfs(DP,now,used):
    if used==N-1:
        return
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x)*P[i][2])
            S+=DP2[i]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(tuple(DP2),next_town+1,used+1)

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y)*P[i][2])
            S+=DP2[i]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(tuple(DP2),next_town+1,used+1)

dfs(tuple(DP1),0,0)

for i in range(1,N):
    ANS[i]=min(ANS[i],ANS[i-1])

print(*ANS)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

DP1=[1<<60]*N

for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))*p

ANS[0]=sum(DP1)

def dfs(DP,now,used):
    if used==N-1:
        return
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x)*P[i][2])
            S+=DP2[i]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        dfs(tuple(DP2),next_town+1,used+1)



        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y)*P[i][2])
            S+=DP2[i]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        dfs(tuple(DP2),next_town+1,used+1)

dfs(tuple(DP1),0,0)

print(*ANS)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

DP1=[1<<60]*N

for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))*p

ANS[0]=sum(DP1)

def dfs(DP,now,used):
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x)*P[i][2])

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],sum(DP2))
        dfs(tuple(DP2),next_town+1,used+1)



        DP2=list(DP)
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y)*P[i][2])

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],sum(DP2))
        dfs(tuple(DP2),next_town+1,used+1)

dfs(tuple(DP1),0,0)

print(*ANS)

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1  & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2  & 0x3333333333333333)
    x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4  & 0x0f0f0f0f0f0f0f0f)
    x = (x & 0x00ff00ff00ff00ff) + (x >> 8  & 0x00ff00ff00ff00ff)
    x = (x & 0x0000ffff0000ffff) + (x >> 16 & 0x0000ffff0000ffff)
    x = (x & 0x00000000ffffffff) + (x >> 32 & 0x00000000ffffffff)
    return x

n = int(input())

x = [0] * n
y = [0] * n
p = [0] * n
s0 = 0
for i in range(n):
    x[i], y[i], p[i] = map(int, input().split())
    s0 += min(abs(x[i]), abs(y[i])) * p[i]
min_s = [s0] * (n + 1)

abs_x = list(map(abs, x))
abs_y = list(map(abs, y))

dist_x = [abs_x[:] for _ in range(1 << n)]
dist_y = [abs_y[:] for _ in range(1 << n)]

for bit in range(1 << n):
    for i in range(n):
        if bit & 1 << i:
            for j in range(n):
                dist_x[bit][j] = min(dist_x[bit][j], abs(x[j] - x[i]))
                dist_y[bit][j] = min(dist_y[bit][j], abs(y[j] - y[i]))
    for i in range(n):
        dist_x[bit][i] *= p[i]
        dist_y[bit][i] *= p[i]

for bit in range(1, 1 << n):
    i = popcount(bit)
    bit_x = bit
    while True:
        bit_y = bit_x ^ bit
        s = 0
        for j in range(n):
            s += min(dist_x[bit_x][j], dist_y[bit_y][j])
        if min_s[i] > s:
            min_s[i] = s
        if bit_x == 0:
            break
        bit_x = (bit_x - 1) & bit

for s in min_s:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

n, *towns = map(int, sys.stdin.buffer.read().split())
xxx = np.array(towns[0::3], dtype=np.int64)
yyy = np.array(towns[1::3], dtype=np.int64)
ppp = np.array(towns[2::3], dtype=np.int64)

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

bit_d = ((np.arange(1 << n)[:, None] & (1 << np.arange(n)))) > 0
precalc_x = abs((xxx[None, :] * bit_d)[..., None] - xxx[None, None, :]).min(axis=1) * ppp[None, :]
precalc_y = abs((yyy[None, :] * bit_d)[..., None] - yyy[None, None, :]).min(axis=1) * ppp[None, :]
kd = bit_d.sum(axis=1)

for bit in range(1 << n):
    k = kd[bit]
    v = bit
    while v:
        ans[k] = min(ans[k], np.minimum(precalc_x[v], precalc_y[v ^ bit]).sum())
        v = (v - 1) & bit
    ans[k] = min(ans[k], np.minimum(precalc_x[0], precalc_y[bit]).sum())

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