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: Wrong Answer

Solution code:
# coding:UTF-8
import sys
from math import factorial
import itertools

MOD = 10 ** 9 + 7
INF = float('inf')

N = int(input())    # 数字
XYP = [list(map(int, input().split())) for _ in range(N)]     # スペース区切り連続数字(行列)

Xlist = set()
Ylist = set()
for x, y, p in XYP:
    Xlist.add(x)
    Ylist.add(y)

for k in range(N+1):
    Mtmp = INF
    for r in range(k+1):
        xpair = itertools.combinations(Xlist, r)
        for xlist in xpair:
            ypair = itertools.combinations(Ylist, k - r)
            for ylist in ypair:
                su = 0
                for n in range(N):
                    m = min(abs(XYP[n][0]), abs(XYP[n][1]))
                    for x in xlist:
                        if abs(XYP[n][0] - x) < m:
                            m = abs(XYP[n][0] - x)
                    for y in ylist:
                        if abs(XYP[n][1] - y) < m:
                            m = abs(XYP[n][1] - y)
                    su += m * XYP[n][2]
                if su < Mtmp:
                    Mtmp = su

    print("{}".format(Mtmp))

Submission status: Wrong Answer

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

n = int(input())
X, Y, P = [], [], []
T = []
U = 0
for _ in range(n):
  x, y, p = map(int, input().split())
  X.append(x)
  Y.append(y)
  P.append(p)
  t = min(abs(x), abs(y))
  T.append(t)
  U += p*t
X = tuple(X)
Y = tuple(Y)
P = tuple(P)
T = tuple(T)
L = [U]*(n+1)
mask = (1<<n)-1
def f(Z):
  res = [[U]*(1<<n) for _ in range(n)]
  for j, z in enumerate(Z):
    for i in range(1<<n):
      if i>>j & 1:
        for q in range(n):
          res[q][i] = min(res[q][i], abs(Z[q]-z))
  return res
A, B = f(X), f(Y)
for i in range(1<<n):
  s = i ^ mask
  j = i
  while j:
    temp = 0
    cnt = 0
    for k, p in enumerate(P):
      temp += p*min(A[k][s], B[k][j], T[k])
      if (s>>k & 1) | (j>>k & 1):
        cnt += 1
    L[cnt] = min(L[cnt], temp)
    j = (j-1) & s
  temp = 0
  cnt = 0
  for k, p in enumerate(P):
    temp += p*min(A[k][s], T[k])
    if (s>>k & 1):
      cnt += 1
  L[cnt] = min(L[cnt], temp)
print(*L, sep="\n")

Submission status: Wrong Answer

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

n = int(input())
X, Y, P = [], [], []
T = []
U = 0
for _ in range(n):
  x, y, p = map(int, input().split())
  X.append(x)
  Y.append(y)
  P.append(p)
  t = min(abs(x), abs(y))
  T.append(t)
  U += p*t
L = [U]*(n+1)
mask = (1<<n)-1
def f(Z):
  res = [[U]*(1<<n) for _ in range(n)]
  for i in range(1<<n):
    for j, z in enumerate(Z):
      if i>>j & 1:
        for q in range(n):
          res[q][i] = min(res[q][i], abs(Z[q]-z))
  return res
A, B = f(X), f(Y)
for i in range(1<<n):
  s = i ^ mask
  j = s
  while j:
    temp = 0
    cnt = 0
    for k, p in enumerate(P):
      temp += p*min(A[k][i], B[k][j], T[k])
      if (i>>k & 1) | (j>>k & 1):
        cnt += 1
    L[cnt] = min(L[cnt], temp)
    j = (j-1) & s
  temp = 0
  cnt = 0
  for k, p in enumerate(P):
    temp += p*A[k][i]
    if (i>>k & 1):
      cnt += 1
  L[cnt] = min(L[cnt], temp)
print(*L, sep="\n")

Submission status: Wrong Answer

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

    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)
    count = 0
    for i in range(1 << N):
        cnt = bin(i).count("1")
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                count += 1
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)
    print(count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product


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

tate = {}
for bit in product(range(2), repeat=N):
    d = [float('inf')] * N
    for i in range(N - 1):
        for j in range(i + 1, N):
            if bit[i]:
                d[i] = 0
                d[j] = min(d[j], abs(T[i][0] - T[j][0]))
            if bit[j]:
                d[j] = 0
                d[i] = min(d[i], abs(T[i][0] - T[j][0]))
    for i in range(N):
        d[i] = min(d[i], abs(T[i][0]))
    tate[tuple(bit)] = d

yoko = {}
for bit in product(range(2), repeat=N):
    d = [float('inf')] * N
    for i in range(N - 1):
        for j in range(i + 1, N):
            if bit[i]:
                d[i] = 0
                d[j] = min(d[j], abs(T[i][1] - T[j][1]))
            if bit[j]:
                d[j] = 0
                d[i] = min(d[i], abs(T[i][1] - T[j][1]))
    for i in range(N):
        d[i] = min(d[i], abs(T[i][1]))
    yoko[tuple(bit)] = d

S = [float('inf')] * (N + 1)
for bit in product(range(3), repeat=N):
    k = 0
    x = []
    y = []
    for b in bit:
        if b == 1:
            x.append(1)
            y.append(0)
            k += 1
        elif b == 2:
            x.append(0)
            y.append(1)
            k += 1
        else:
            x.append(0)
            y.append(0)
    s = 0
    dx = tate[tuple(x)]
    dy = yoko[tuple(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: Wrong Answer

Solution code:
import numpy as np
import itertools

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

X = np.unique(XYP[:, 0])
Y = np.unique(XYP[:, 1])

ans = [None] * (N + 1)
for x in itertools.product([0, 1], repeat=len(X)):
    for y in itertools.product([0, 1], repeat=len(Y)):
        K = sum(x) + sum(y)
        if K > N:
            continue

        RX = [0]
        RY = [0]
        for x2 in range(len(x)):
            if x[x2]:
                RX.append(X[x2])
        for y2 in range(len(y)):
            if y[y2]:
                RY.append(Y[y2])

        s = 0
        for n in range(N):
            xm = np.abs(np.array(RX) - XYP[n][0]).min()
            ym = np.abs(np.array(RY) - XYP[n][1]).min()
            s += XYP[n][2] * min(xm, ym)

        if ans[K] is None or ans[K] > s:
            ans[K] = s

for k in range(len(ans)):
    print(ans[k])

Submission status: Wrong Answer

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


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

    # bitという道路群を建設したときの，各集落iの評価距離
    for bit in range(1 << N):
        for i in range(N):
            X_dist[bit][i] = abs(T[i][0])
            Y_dist[bit][i] = abs(T[i][1])
            for k in range(N):
                if bit & (1 << k):
                    X_dist[bit][i] = \
                        min(X_dist[bit][i], abs(T[i][0] - T[k][0]))
                    Y_dist[bit][i] = \
                        min(Y_dist[bit][i], 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 += 1 << i
                cnt += 1
            elif b == 1:
                # y = a
                y_bit += 1 << 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: Wrong Answer

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: Wrong Answer

Solution code:
import time,random

def subset(n):
    temp=n
    while True:
        yield temp
        if temp==0:
            break
        temp=(temp-1)&n

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

xx=[[abs(city[j][0]) for j in range(N)] for i in range(2**N)]
yy=[[abs(city[j][1]) for j in range(N)] for i in range(2**N)]
X=[city[i][0] for i in range(N)]
Y=[city[i][1] for i in range(N)]

def elex(n):
    for i in range(N):
        if n>>i &1:
            yield X[i]

def eley(n):
    for i in range(N):
        if n>>i &1:
            yield Y[i]

def elen(n):
    for i in range(N):
        if n>>i&1:
            yield i

for i in range(2**N):
    for j in elen(2**N-i):
        for k in elex(i):
            xx[i][j]=min(xx[i][j],abs(city[j][0]-k))
        for k in eley(i):
            yy[i][j]=min(yy[i][j],abs(city[j][1]-k))

ans=[10**15 for i in range(N+1)]
for i in range(2**N):
    rest=[j for j in range(N) if i>>j &1==0]
    count=N-len(rest)
    for cond in subset(i):
        temp=sum(min(xx[cond][j],yy[i-cond][j])*city[j][2] for j in rest)
        ans[count]=min(ans[count],temp)

for i in range(N+1):
    print(ans[i])
#print(time.time()-start)

Submission status: Wrong Answer

Solution code:
n=int(input())
xyp=[list(map(int,input().split()))for _ in range(n)]
ans=0
for i in range(3**n):
  for j in range(n):ans+=1
print(ans)

Submission status: Wrong Answer

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(1):
    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: Wrong Answer

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)]
    for i in range(n+1):
        dp[0][i] = 0
    for i in range(1,n+1):
        dp[i][0] = dp[i-1][0] + abs(val_list[i-1][0] * val_list[i-1][1])

    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)
            # 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 = min(next_dist, sum)

            for j in range(n):
                dp[r][j+1] = min(dp[r][j+1], 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: Wrong Answer

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,  len(x_lines_list)-1)]
            post_x = x_lines_list[min(v+1, 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[min(v, len(y_lines_list) - 1)]
            post_y = y_lines_list[min(v + 1, 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()

Submission status: Wrong Answer

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]
    ys=[10**20]
    for i in range(n):
        if bitt&(1<<i):
            xs.append(xyp[i][0])
            ys.append(xyp[i][1])
    xs.sort()
    ys.sort()
    xx.append(xs)
    yy.append(ys)
for trit in range(1,3**n):
    zbit=0
    xbit=0
    ybit=0
    for i in range(n):
        if trit%3==0:zbit+=1
        if trit%3==1:xbit+=1<<i
        if trit%3==2:ybit+=1<<i
        trit//=3
    if zbit==0:continue
    anss=[min(abs(x),abs(y))*p for x,y,p in xyp]
    if xbit:
        notxbits=[0 if xbit&(1<<i) else 1 for i in range(n)]
        xs=xx[xbit]
        i=0
        for j in range(n):
            x=xyp[j][0]
            if 0==(xbit&(1<<j)):
                while abs(xs[i]-x)>abs(xs[i+1]-x):i+=1
                anss[j]=min(anss[j],abs(xs[i]-x)*xyp[j][2])
            else:anss[j]=0
    if ybit:
        notybits=[0 if ybit&(1<<i) else 1 for i in range(n)]
        ys=yy[ybit]
        i=0
        for j in range(n):
            y=xyp[j][1]
            if 0==(ybit&(1<<j)):
                while abs(ys[i]-y)>abs(ys[i+1]-y):i+=1
                anss[j]=min(anss[j],abs(ys[i]-y)*xyp[j][2])
            else:anss[j]=0
    ans[n-zbit]=min(ans[n-zbit],sum(anss))
print(*ans)

Submission status: Wrong Answer

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

DX = [[0] * n for s in range(2**n)]
DY = [[0] * n for s in range(2**n)]
for s in range(2**n):
    for i in range(n):
        DX[s][i] = abs(X[i]) * P[i]
        DY[s][i] = abs(Y[i]) * P[i]
        for j in range(n):
            if s & (1 << j):
                DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
                DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])

A = [10**20] * (n + 1)
for s in range(3**n):
    tmp = s
    c, sx, sy = 0, 0, 0
    for i in range(n):
        if tmp % 3 == 0:
            continue
        if tmp % 3 == 1:
            sx += 2**i
        if tmp % 3 == 2:
            sy += 2**i
        c += 1
        tmp //= 3
    d = 0
    for i in range(n):
        d += min(DX[sx][i], DY[sy][i])
    A[c] = min(A[c], d)
print(*A, sep="\n")

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
people = []
for _ in range(n):
  x, y, p = map(int, input().split())
  people.append((x, y, p))
people_sorted = sorted(people, key=lambda x: -x[2])

points = []
for i in range(n+1):
  if i == 0:
    total = 0
    for x, y, p in people_sorted:
      total += p * min(x, y)
    print(total)
  else:
    x, y, p = people_sorted[i-1]
    points.append((x, 0))
    points.append((0, y))
    all_total = 10**20
    for v in itertools.permutations(points, i):
      total = 0
      for j in range(i, n):
        x, y, p = people_sorted[j]
        dist = p * min(x, y)
        for a, b in v:
          if a == 0:
            k = p * abs(y-b)
          else:
            k = p * abs(x-a)
          if dist > k:
            dist = k
        total += dist
      if all_total > total:
        all_total = total
    print(all_total)

Submission status: Wrong Answer

Solution code:
from itertools import product
n = int(input())
XYP = [tuple(map(int, input().split())) for i in range(n)]
X = [x for x, y, p in XYP]
Y = [y for x, y, p in XYP]
P = [p for x, y, p in XYP]

DX = {s: [1 << 30] * n for s in product(range(2), repeat=n)}
DY = {s: [1 << 30] * n for s in product(range(2), repeat=n)}
for s in product(range(2), repeat=n):
    for i in range(n):
        DX[s][i] = abs(X[i]) * P[i]
        DY[s][i] = abs(Y[i]) * P[i]
        for j in range(n):
            if s[j] == 1:
                DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
                DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])

A = [1 << 30] * (n + 1)
for s in product(range(3), repeat=n):
    c = s.count(1) + s.count(2)
    sx = tuple(int(s[i] == 1) for i in range(n))
    sy = tuple(int(s[i] == 2) for i in range(n))
    A[c] = min(A[c], sum([min(DX[sx][i], DY[sy][i]) for i in range(n)]))
print(*A, sep="\n")

Submission status: Wrong Answer

Solution code:
from itertools import product
n = int(input())
XYP = [tuple(map(int, input().split())) for i in range(n)]
X = [x for x, y, p in XYP]
Y = [y for x, y, p in XYP]
P = [p for x, y, p in XYP]
A = [1 << 30] * (n + 1)
for s in product(range(3), repeat=n):
    c = s.count(1) + s.count(2)
    d = 0
    for i in range(n):
        di = min(abs(X[i]), abs(Y[i])) * P[i]
        for j in range(n):
            if s[j] == 1:
                di = min(di, abs(X[i] - X[j]) * P[i])
            if s[j] == 2:
                di = min(di, abs(Y[i] - Y[j]) * P[i])
        d += di
    A[c] = min(A[c], d)
print(*A, sep="\n")

Submission status: Wrong Answer

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

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


def main():
    N = int(input())
    P = read_lists(N)
    # N = 15
    # P = [(i ** 2 + 1, i ** 2 + 1, i ** 2 + 1) for i in range(N)]
    
    C = [1 << 62] * (N + 1)
    # CX = [None for _ in range(2 ** N)]
    # CY = [None for _ in range(2 ** N)]
    CX = [[1 << 31] * N for _ in range(2 ** N)]
    CY = [[1 << 31] * N for _ in range(2 ** N)]
    LX = [0] * (2 ** N)
    LY = [0] * (2 ** N)
    for K in range(2 ** N):
        X = {0}
        Y = {0}
        for i in range(N):
            if (K >> i) & 1:
                X.add(P[i][0])
                Y.add(P[i][1])
         
        # CXX = [0] * N
        # CYY = [0] * N
        for j, (xp, yp, cp) in enumerate(P):
            for x in X:
                # CXX[j] = min(abs(xp - x) * cp, CXX[j])
                CX[K][j] = min(abs(xp - x) * cp, CX[K][j])
            for y in Y:
                CY[K][j] = min(abs(yp - y) * cp, CY[K][j])
                # CYY[j] = min(abs(yp - y) * cp, CYY[j])
            
        LX[K] = len(X)
        LY[K] = len(Y)
        # CX[K] = tuple(CXX)
        # CY[K] = tuple(CYY)

    for T in itertools.product((0, 1, 2), repeat=N):
        txy = [0, 0, 0]
        for i, t in enumerate(T):
            txy[t] += (1 << i)

        p = LX[txy[1]] + LY[txy[2]] - 2
        if C[p] == 0:
            continue
        # c = sum(1 for n in range(N))
        c = 0
        for n in range(N):
            # c += 1
            c += min(CX[txy[1]][n], CY[txy[2]][n])
        C[p] = min(C[p], c)

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


if __name__ == "__main__":
    main()