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:
from itertools import combinations

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

x_better = [True] * N
for station in range(N):
    walksums = []
    for i in range(2):
        xs = [0]
        ys = [0]
        for j in range(1):
            if i & (1 << j):
                xs.append(XYPs[station][0])
            else:
                ys.append(XYPs[station][1])
        walksum = 0
        for X, Y, P in XYPs:
            mindis = min(min([abs(X - x) for x in xs]), min([abs(Y - y) for y in ys]))
            walksum += mindis * P
        walksums.append(walksum)
    x_better[station] = walksums[0] < walksums[1]

for K in range(N+1):
    minwalksum = 10 ** 18
    for stations in combinations(range(N), K):
        xs = [0]
        ys = [0]
        for j in range(K):
            if x_better[stations[j]]:
                xs.append(XYPs[stations[j]][0])
            else:
                ys.append(XYPs[stations[j]][1])
        walksum = 0
        for X, Y, P in XYPs:
            mindis = min(min([abs(X - x) for x in xs]), min([abs(Y - y) for y in ys]))
            walksum += mindis * P
        minwalksum = min(minwalksum, walksum)
    print(minwalksum)

Submission status: Wrong Answer

Solution code:
import itertools
def main():
    N=[list(map(int,input().split())) for _ in range(int(input()))]
    Xr = set([0])
    Yr = set([0])
    ans = [calc(N,Xr,Yr)]
    for i in range(1,len(N)+1):
        ans_can = []
        for n in itertools.combinations(N,i):
            ans_can.append(test(n,N,Xr,Yr))
        
        ans.append(min(ans_can))
    for a in ans:
        print(a)

def test(n, N, Xr, Yr):
    tX = Xr.copy()
    tY = Yr.copy()
    ans = []
    for nn in itertools.product([0,1], repeat=len(n)):
        for i, v in enumerate(nn):
            if v == 0:
                tX.add(n[i][0])
            else:
                tY.add(n[i][1])
        ans.append(calc(N,tX,tY))
    return min(ans)

def calc(N, Xr, Yr):
    ans = []
    for n in N:
        if n[0] in Xr or n[1] in Yr:
            ans.append(0)
        else:
            mX = min(abs(n[0]-i) for i in Xr)
            mY = min(abs(n[1]-i) for i in Yr)
            ans.append(min(mX,mY)*n[2])
    return sum(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


def main():
    from itertools import combinations
    import bisect
    N = int(input())
    XYP = [tuple(map(int, input().split())) for i in range(N)]

    S = 0
    for x, y, p in XYP:
        S += min(abs(x), abs(y))*p

    print(S)

    dpX = [[0]*N for i in range(2**N)]

    dpY = [[0]*N for i in range(2**N)]

    for i in range(2**N):
        arr = []
        for j in range(N):
            if (i >> j) % 2 == 1:
                if (len(arr) == 0 or arr[-1] < 0) and XYP[j][0] > 0:
                    arr.append(0)
                arr.append(XYP[j][0])

        for j in range(N):
            if (i >> j) % 2 == 1:
                dpX[i][j] = 0
            else:
                X = XYP[j][0]
                id = bisect.bisect_left(arr, X)
                ret = abs(X)
                if id < len(arr):
                    ret = min(ret, arr[id] - X)
                if id > 0:
                    ret = min(ret, X - arr[id-1])
                dpX[i][j] = ret * XYP[j][2]

    for i in range(2**N):
        arr = []
        for j in range(N):
            if (i >> j) % 2 == 1:
                if (len(arr) == 0 or arr[-1] < 0) and XYP[j][1] > 0:
                    arr.append(0)
                arr.append(XYP[j][1])

        for j in range(N):
            if (i >> j) % 2 == 1:
                dpY[i][j] = 0
            else:
                Y = XYP[j][1]
                id = bisect.bisect_left(arr, Y)
                ret = abs(Y)
                if id < len(arr):
                    ret = min(ret, arr[id] - Y)
                if id > 0:
                    ret = min(ret, Y - arr[id-1])
                dpY[i][j] = ret * XYP[j][2]

    ans = [S]*N

    for i in range(1, N+1):
        for j in range(i+1):
            k = i - j
            for x in combinations(range(N), j):
                idx = 0
                s = set(range(N))
                for xx in x:
                    idx += 1 << xx
                    s.remove(xx)
                dX = dpX[idx]
                for y in combinations(s, k):
                    tmp = 0
                    idy = 0
                    for yy in y:
                        idy += 1 << yy
                    if idx & idy > 0:
                        continue
                    dY = dpY[idy]
                    tmp = 0
                    for x, y in zip(dX, dY):
                        if x > y:
                            tmp += y
                        else:
                            tmp += x
                    if tmp < ans[i-1]:
                        ans[i-1] = tmp
    for i in range(N):
        print(ans[i])


main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    p = LIR(n)
    p.sort()
    m = 3**n
    s = 0
    for i,(x,y,num) in enumerate(p):
        d = min(abs(x),abs(y))
        s += num*d
        p[i].append(d)
    ans = [s]*(n+1)
    ans[-1] = 0
    for i in range(n):
        x,y,num,d = p[i]
        for j in range(n):
            if i == j:
                continue
            nx,ny = p[j][:2]
            nd = min(abs(x-nx),abs(y-ny))
            if nd < d:
                d = nd
        ns = d*num
        if ns < s:
            s = ns
    ans[-2] = s
    for b in range(m):
        lx = []
        ly = []
        cnt = 0
        res = b
        for x,y,num,d in p:
            j = res%3
            if j:
                cnt += 1
                if j == 1:
                    lx.append(x)
                else:
                    ly.append(y)
            res //= 3
        if cnt+1 >= n:
            continue
        ly.sort()
        s = 0
        ans_ = ans[cnt]
        for x,y,num,d in p:
            i = bisect.bisect_left(lx,x)-1
            if i >= 0:
                nd = x-lx[i]
                if nd < d:
                    d = nd
            i += 1
            if i < len(lx):
                nd = lx[i]-x
                if nd < d:
                    d = nd
            i = bisect.bisect_left(ly,y)-1
            if i >= 0:
                nd = y-ly[i]
                if nd < d:
                    d = nd
            i += 1
            if i < len(ly):
                nd = ly[i]-y
                if nd < d:
                    d = nd
            s += d*num
            if s >= ans_:
                break
        else:
            if s == 0:
                for i in range(cnt,n+1):
                    ans[i] = 0
                break
            ans[cnt] = s
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def solve(X, Y, P, N):
    S = [-1 for i in range(N+1)]
    T = [[0 for j in range(N+1)] for i in range(N+1)]
    U = [i for i in range(1, N+1)] + [-i for i in range(1, N+1)]
    for K in range(0, N+1):
        if K == 0:
            s = 0
            for i in range(1, N+1):
                t = min(abs(X[i]), abs(Y[i])) * P[i]
                s += t
                T[0][i] = t
            S[0] = s
        elif S[K-1] == 0:
            S[K] = 0
        else:
            u = float('inf')
            min_K = 0
            for data in U:
                if data < 0:
                    s = 0
                    for i in range(1, N+1):
                        t = min(T[K-1][i], abs(X[i]-X[-data]))*P[i]
                        s += t
                        T[K][i] = min(t, T[K][i])
                    if s < u:
                        u = s
                        min_K = K
                else:
                    s = 0
                    for i in range(1, N+1):
                        t = min(T[K-1][i], abs(Y[i]-Y[data]))*P[i]
                        s += t
                        T[K][i] = min(t, T[K][i])
                    if s < u:
                        u = s
                        min_K = K
            S[K] = u
            U.remove(min_K)
    return S
N = int(input())
X = [0]
Y = [0]
P = [0]
for i in range(N):
    x, y, p = map(int, input().split())
    X.append(x)
    Y.append(y)
    P.append(p)
print(solve(X, Y, P, N))

Submission status: Wrong Answer

Solution code:
N = int(input())

max_x = 0
min_x = 0
max_y = 0
min_y = 0

xyp_matrix = []
for n in range(N):
    
    l = list(map(int, input().split()))
    xyp_matrix.append(l)
    
    if l[0] > max_x:
        max_x =  l[0]
    if l[0] < min_x:
        min_x =  l[0]
    if l[1] > max_y:
        max_y =  l[1]
    if l[1] < min_y:
        min_y =  l[1]
        
        
import numpy as np
item = list(range((max_x - min_x +1) + (max_y - min_y + 1)))
result = [np.inf] * (N + 1)


n = len(item)
for i in range(2 ** n):
    bag = []
    #print("pattern {}: ".format(i), end="")
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(j)  # フラグが立っていたら bag に果物を詰める
    #print(bag)
    
    if len(bag) > N:
        continue
    
    total_cost = 0
    for xyp in xyp_matrix:
        x = xyp[0]
        y = xyp[1]
        
        min_dis = min(abs(x), abs(y))
        for b in bag:
            if b <= max_x - min_x +1:
                min_dis = min(min_dis, abs(b - x))
            else:
                min_dis = min(min_dis, abs(b - (max_x - min_x +1) - y))
        
        cost = xyp[2] * min_dis
        total_cost += cost
    
    result[len(bag)] = min(result[len(bag)], total_cost)
        
        
for r in result:
    print(r)

Submission status: Wrong Answer

Solution code:
n = int( input() )
x = []
y = []
p = []
for _ in range( n ):
    x_i, y_i, p_i = map( int, input().split() )
    if x_i == 0 or y_i == 0:
        p_i = 0
    x.append( x_i )
    y.append( y_i )
    p.append( p_i )

rail_h = [ 0 ]
rail_v = [ 0 ]

def nearest( city, r_v, r_h ):
    nearest_x = [ abs( v - x[ city ] ) for v in r_v ]
    nearest_y = [ abs( h - y[ city ] ) for h in r_h ]
    return min( min( nearest_x ), min( nearest_y ) )

def sum_steps():
    min_s = float( "Inf" )
    min_xy = 0
    pm = 0
    for x_i in x:
        s_i = 0
        for i in range( n ):
            d = nearest( i, rail_v + [ x_i ], rail_h )
            s_i += d * p[ i ]
        if min_s > s_i:
            min_s = s_i
            min_xy = x_i
            pm = 1
    for y_i in y:
        s_i = 0
        for i in range( n ):
            d = nearest( i, rail_v, rail_h + [ y_i ] )
            s_i += d * p[ i ]
        if min_s > s_i:
            min_s = s_i
            min_xy = y_i
            pm = -1
    return min_s, min_xy, pm

s = 0
for i in range( n ):
    d = nearest( i, rail_v, rail_h )
    s += d * p[ i ]
    if d == 0:
        p[ i ] = 0
print( s )

for k in range( n ):
    s = 0
    s_i, xy_i, pm = sum_steps()
    s += s_i
    print( s )

    if pm > 0:
        rail_v.append( xy_i )
        for i in range( n ):
            if x[ i ] == xy_i:
                p[ i ] = 0
    else:
        rail_h.append( xy_i )
        for i in range( n ):
            if y[ i ] == xy_i:
                p[ i ] = 0

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations_with_replacement,product
def input(): return sys.stdin.readline().rstrip()
def kyori(xlist,ylist,x,y):
    return min(min(map(lambda m: abs(m-x),xlist)),min(map(lambda u: abs(u-y),ylist)))

 
def main():
    n=int(input())
    li=[]
    x=set()
    y=set()
    for _ in range(n):
        xi,yi,pi=map(int, input().split())
        li.append([xi,yi,pi])
        x.add(xi)
        y.add(yi)
    if 0 in x:
        x.remove(0)
    if 0 in y:
        y.remove(0)    
    x=list(x)
    y=list(y)
    klist=[10**15]*(n*2)
    for xr in list(product([0,1],repeat=len(x))):
        for yr in list(product([0,1],repeat=len(y))):
            k=sum(xr)+sum(yr)
            if k>n or klist[k]==0:
                continue
            nowx={0}
            for i in range(len(x)):
                if xr[i]==1:
                    nowx.add(x[i])
            nowy={0}
            for i in range(len(y)):
                if yr[i]==1:
                    nowy.add(y[i])
            nowx=list(nowx)
            nowy=list(nowy)
            cost = 0
            for lis in li:
                cost+=kyori(nowx,nowy,lis[0],lis[1])*lis[2]
            klist[k]=min(klist[k],cost)

    for g in range(n+1):
        print(klist[g])


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import copy
N=int(input())
List=[list(map(int,input().split())) for i in range(N)]
x_no_list=[]
y_no_list=[]
x_no_list.append(0)
y_no_list.append(0)
l2 = copy.copy(x_no_list)
l3 = copy.copy(y_no_list)
def min_x(t):
    s=abs(t-x_no_list[0])
    for i in range(len(x_no_list)):
        if s > abs(t-x_no_list[i]):
            s=abs(t-x_no_list[i])
    return s
def min_y(t):
    s=abs(t-y_no_list[0])
    for i in range(len(y_no_list)):
        if s > abs(t-y_no_list[i]):
            s=abs(t-y_no_list[i])
    return s
def soukyori(List):
    s=0
    for i in range(0,len(List)):
        s+=min(min_x(List[i][0]),min_y(List[i][1]))*List[i][2]
    return s
print(soukyori(List))
p=1
goal=soukyori(List)
while goal!=0:
    x_no_list.append(List[0][0])
    sub=soukyori(List)
    sub1=0
    sub2=100
    for i in range(1,N):
        x_no_list.pop(-1)
        x_no_list.append(List[i][0])
        if sub>soukyori(List):
            sub=soukyori(List)
            sub1=i
    x_no_list.pop(-1)
    for i in range(0,N):
        y_no_list.append(List[0][1])
        if sub>soukyori(List):
            sub=soukyori(List)
            sub2=i
            sub1=100
        y_no_list.pop(-1)
    if sub1==100:
        y_no_list.append(List[sub2][1])
    else:
        x_no_list.append(List[sub1][0])
    print(soukyori(List))
    p=+1
    goal=soukyori(List)
q=N+1-p
while q!=1:
    print(0)
    q-=1

Submission status: Wrong Answer

Solution code:
import itertools
def solve():
  N = int(input())
  XYP = [[0 for _ in range(3)] for _ in range(N)]
  HH = [[0 for _ in range(2)] for _ in range(N)]
  VV = [[0 for _ in range(2)] for _ in range(N)]
  SS = [0]*N
  v1 = 0
  h1 = 0
  for i in range(N):
    X,Y,P = map(int,input().split())
    XYP[i] = [X,Y,P]
    ve = False
    he = False
    for j in range(i):
      if VV[j][0] == X:
        ve = True
        VV[j][1]+=P
      if HH[j][0] == Y:
        he = True
        HH[j][1]+=P
    if not ve:
      VV[i][0] = X
      VV[i][1] = P
      v1+=1
    if not he:
      HH[i][0] = Y
      HH[i][1] = P
      h1+=1
    if abs(X)>abs(Y):
      SS[i]+=abs(Y)*P
    else:
      SS[i]+=abs(X)*P
  print(sum(SS))
  HH.sort(key=lambda x: x[1],reverse=True)
  VV.sort(key=lambda x: x[1], reverse=True)
  SS0 = sum(SS)
  for i in range(1,N):
    SSmx = SS0
    for j in range(i+1):
      SS = [0]*N
      for n in range(N):
        s = abs(XYP[n][0])
        for v in range(j):
          if abs(VV[v][0]-XYP[n][0])<s:
            s=abs(VV[v][0]-XYP[n][0])
        for h in range(i-j):
          if abs(HH[h][0]-XYP[n][1])<s:
            s=abs(HH[h][0]-XYP[n][1])
        SS[n] = s*XYP[n][2]
      if sum(SS)<SSmx:
        SSmx = sum(SS)
    print(SSmx)
  print(0)      

           
solve()

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
n = int(input())
ts = [list(map(int, input().split())) for _ in range(n)]
res = 0
for i in ts:
    tmp = min(abs(i[0]),abs(i[1]))
    res += tmp * i[2]
print(res)

bars = {}
for i in ts:
    tmp = min(abs(i[0]),abs(i[1]))
    if "x:"+str(i[0]) not in bars:
        bars["x:"+str(i[0])] = 1
    if "y:"+str(i[1]) not in bars:
        bars["y:"+str(i[1])] = 1
for k in range(1,n+1):
    res = float('inf')
    for this_bars in comb(bars,k):
        tmp = 0
        for this_bars in this_bars:
            for t in ts:
                if this_bars[0] == 'x':
                    tmp += abs(t[0] - int(this_bars[2:]))
                else:
                    tmp += abs(t[1] - int(this_bars[2:]))
        res = min(res, tmp)
    print(res)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import Counter
from itertools import product, combinations

N = int(input())

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

# P の大きい順にソート
px, py, p = zip(*sorted(zip(X, Y, P), key=lambda x: -x[2]))

# 考えるべき最大の K 、つまり K >= maxK で distance = 0 となる maxK を考える
cx, cy = Counter(X), Counter(Y)
maxK = N
for i in range(N):
    if cx[X[i]] >= 2:
        maxK -= 1
    elif cy[Y[i]] >= 2:
        maxK -= 1
maxK += len([v for v in cx.values() if v >= 2]) + len([v for v in cy.values() if v >= 2])

# print(f"maxK = {maxK}")

# こうすればあとは K = 0, 1, 2, ..., maxK-1 で考えればよい
# しかもこの maxK は最大で 15 なのでなんか全探索とかいけそう？
# たかだか 2^15 < 40000 通り

# K = 0
distance = sum([P[i] * min(abs(X[i]), abs(Y[i])) for i in range(N)])
print(distance)

# 通る点
# 同一直線状に複数点があるものは候補に含まれるので先に入れとく（そんなに多くないでしょきっと）
points = [(x, y) for x, y in zip(X, Y) if (cx[x] >= 2 or cy[y] >= 2)]

for K in range(1, maxK):
    # print(f"K = {K}")
    # K 個の通る点を選択
    points.append((px[K-1], py[K-1]))
    points = list(set(points))
    # print(f"points = {points}")
    # 2^K 通りの全探索を実施
    # points のそれぞれに対し、 直線 x = X[i] or y = Y[i] のどちらを選択するかで評価
    ans = float("inf")
    for now in product(range(2), repeat=len(points)):
        # now[i] == 0 ならば x = X[i] を選択
        lines = []
        for i in range(len(points)):
            if now[i] == 0:
                lines.append(("x", points[i][0]))
            else:
                lines.append(("y", points[i][1]))
        # print(f"  lines: {lines}")
        # lines から K 本とる
        for v in combinations(lines, K):
            # 実際の通る直線
            xlines, ylines = [], []
            for u in v:
                if u[0] == "x":
                    xlines.append(u[1])
                else:
                    ylines.append(u[1])
            # コストの計算
            res = 0
            for i in range(N):
                xcost = abs(X[i])
                for j in range(len(xlines)):
                    xcost = min(xcost, abs(X[i] - xlines[j]))
                ycost = abs(Y[i])
                for j in range(len(ylines)):
                    ycost = min(ycost, abs(Y[i] - ylines[j]))
                res += P[i] * min(xcost, ycost)
            # print(f"  now res = {res}")
            ans = min(ans, res)
    print(ans)

for _ in range(N - maxK + 1):
    print(0)

Submission status: Wrong Answer

Solution code:
class Pt(object):
    def __init__(self, x, y, p) -> None:
        self.x = x
        self.y = y
        self.p = p
        self.d = min(abs(x), abs(y))


def calc_cost(lst_pt, idx):
    cst = 0
    if idx is None:
        for pt in lst_pt:
            cst += pt.p * pt.d
        return cst

    cst_x = 0
    for pt in lst_pt:
        if pt.d == 0:
            continue
        d_x = abs(pt.x - lst_pt[idx].x)
        cst_x += pt.p * min(pt.d, d_x)

    cst_y = 0
    for pt in lst_pt:
        if pt.d == 0:
            continue
        d_y = abs(pt.y - lst_pt[idx].y)
        cst_y += pt.p * min(pt.d, d_y)
    cst = min(cst_x, cst_y)

    return cst


def update_pt(lst_pt, idx):
    for i, pt in enumerate(lst_pt):
        if pt.d == 0:
            continue
        d_x = abs(pt.x - lst_pt[idx].x)
        d_y = abs(pt.y - lst_pt[idx].y)
        pt.d = min(pt.d, d_x, d_y)
        lst_pt[i] = pt
    return lst_pt


def main():
    n = int(input())
    lst_pt = []
    lst_d = []
    for _ in range(n):
        x, y, p = [int(v) for v in input().split(' ')]
        lst_pt.append(Pt(x, y, p))
        lst_d.append(min(x, y))

    fin_flag = False
    min_cst = calc_cost(lst_pt, None)
    print(min_cst)
    for _ in range(n):
        if fin_flag:
            print(0)
            continue

        min_idx = None
        for i in range(n):
            # if lst_pt[i].d == 0:
            #     continue
            cst = calc_cost(lst_pt, i)
            if min_cst is None or min_cst > cst:
                min_idx = i
                min_cst = cst

        if min_idx is not None:
            lst_pt = update_pt(lst_pt, min_idx)
        print(min_cst)
        fin_flag = min_cst == 0


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[LI() for _ in range(n)]

  ans=[]
  chokusen=[['X',0],['Y',0]]

  d_sum=0
  for x,y,p in l:
    d=inf
    for xory,zahyo in chokusen:
      if xory=='X':
        d=min(d,abs(y-zahyo)*p)
      else:
        d=min(d,abs(x-zahyo)*p)
    d_sum+=d
  ans.append(d_sum)

  for _ in range(n):
    koho=[]
    for _x,_y,_p in l:

      d_sum1=0
      chokusen.append(('X',_x))
      for x,y,p in l:
        d=inf
        for xory,zahyo in chokusen:
          if xory=='X':
            d=min(d,abs(y-zahyo)*p)
          else:
            d=min(d,abs(x-zahyo)*p)
        d_sum1+=d

      koho.append(d_sum1)
      chokusen.pop()

      d_sum2=0
      chokusen.append(('Y',_y))
      for x,y,p in l:
        d=inf
        for xory,zahyo in chokusen:
          if xory=='X':
            d=min(d,abs(y-zahyo)*p)
          else:
            d=min(d,abs(x-zahyo)*p)
        d_sum2+=d

      koho.append(d_sum2)
      chokusen.pop()

      # print(koho)

    min_ind=koho.index(min(koho))
    _koho=min_ind//2
    if min_ind%2==0:
      ank='X'
      val=l[_koho][0]
    else:
      ank='Y'
      val=l[_koho][1]
    _koho=min_ind//2
    chokusen.append((ank,val))

    d_sum=0
    for x,y,p in l:
      d=inf
      for xory,zahyo in chokusen:
        if xory=='X':
          d=min(d,abs(y-zahyo)*p)
        else:
          d=min(d,abs(x-zahyo)*p)
      d_sum+=d
    ans.append(d_sum)
    # print(chokusen)

  for x in ans:
    print(x)

main()
# print(main())

Submission status: Wrong Answer

Solution code:

n = int(input())
xyp = []
XY = []
for _ in range(n):
    x, y, p = map(int, input().split())
    xyp.append((x, y, p))
    XY.append((x, 0))
    XY.append((y, 1))

anss = [10**9] * (n+1)
for _ in range(n):
    x_cost_ans = 10**9
    for _ in range(2**n):
        for i in range(2**len(XY)):
            train_count = bin(i).count('1')
            if train_count >= n:
                # 考えないパターン
                continue

            x_trains = [0]
            y_trains = [0]
            for j in range(len(XY)):
                if (i>>j)&1:
                    corr, xy = XY[j]
                    if xy == 0:
                        #xに通す
                        x_trains.append(corr)
                    else:
                        #yに通す
                        y_trains.append(corr)
                cost = 0
                for x, y, p in xyp:
                    x_dist = min(map(lambda xx: abs(xx-x), x_trains))
                    y_dist = min(map(lambda yy: abs(yy-y), y_trains))
                    cost += min(x_dist, y_dist)*p
                    if anss[train_count] < cost:
                        break

                anss[train_count] = min(anss[train_count], cost)

for ans in anss:
    if ans == 10**9:
        print(0)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

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

towns.sort(reverse=True)


def cost(xlist, ylist):
    total = 0
    for p, x, y in towns:
        total += p * min(min([abs(x - dx) for dx in xlist]), min([abs(y - dy) for dy in ylist]))
    return total


print(cost([0], [0]))

for k in range(1, N + 1):
    mincost = 10 ** 12
    for bits in product((True, False), repeat=k):
        x = {0}
        y = {0}
        for index, bit in enumerate(bits):
            if bit:
                x.add(towns[index][1])
            else:
                y.add(towns[index][2])
        mincost = min(mincost, cost(x, y))
    print(mincost)

Submission status: Wrong Answer

Solution code:
N = int(input())
XYP = []
for _ in range(N):
    t = list(map(int,input().split()))
    XYP.append([t[0],t[1],t[2]])

def calc():
    rev = 0
    for i in range(N):
        rev += min(XYP[i][0], XYP[i][1]) * XYP[i][2]
    return rev

sum = float('inf')
for i in range(N+1):
    if sum == 0:
        print(0)
        continue
    
    # if i != 0:
        

    sum = calc()
    print(sum)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import numpy as np

n = int(input())

c = []
x = set()
y = set()
s0 = 0
for _ in range(n):
    xx, yy, p = map(int, input().split())
    # 元々鉄道上
    if xx == 0 or yy == 0:
        continue
    c.append((xx, yy, p))
    s0 += (min(abs(xx), abs(yy))*p)
    x.add(xx)
    y.add(yy)

# 0個選択
print(s0)

l = [[min(abs(xx), abs(yy), abs(lx-xx))*p for xx, yy, p in c] for lx in x]
l2 = [[min(abs(xx), abs(yy), abs(ly-yy))*p for xx, yy, p in c] for ly in y]
l.extend(l2)
l = np.array(l)
ln = l.shape[0]

for i in range(1, len(c)+1):
    # lからi個選んだ各項目の最小値
    m = 10**20
    for x in combinations(range(ln), i):
        mm = np.sum(np.min(l[x, :], axis=0))
        if mm < m:
            m = mm
            if m == 0:
                break
    print(m)

for i in range(len(c)+1, n+1):
    print(0)