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
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	labs = []
	total = 0
	for i in range(N):
		X,Y,P = inputMap()
		zeX = abs(X)
		zeY = abs(Y)
		tmp = min(zeX,zeY) * P
		labs.append((tmp,X,Y,P))
		total += tmp

	print(total)
	print(labs)
	for i in range(N-1):
		score = inf
		rere = 0
		for j,val in enumerate(labs):
			S,X,Y,P = val
			score_tmp = 0
			flg = False
			for k,valval in enumerate(labs):
				if j == k:
					continue
				SS,XX,YY,PP = valval
				zeX = abs(XX)
				zeX2 = abs(X-YY)
				zeY = abs(YY)
				zeY2 = abs(Y-XX)
				tmp1 = min(zeX,zeX2,YY) * PP
				tmp2 = min(zeY,zeY2,XX) * PP
				score_tmp += min(tmp1,tmp2)
			if score > score_tmp:
				score = score_tmp
				rere = j
				if tmp1 < tmp2:
					flg = True
		print(score)

	print(0)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

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)
    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:
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)]
    XorY = [True for _ in range(N)]  # X軸方向に直線を張った方がお得

    for i in range(N):
        x = T[i][0]
        y = T[i][1]
        x_dist = 0
        y_dist = 0
        for j in range(N):
            if i == j:
                continue
            x_dist += T[j][2]*abs(T[j][0] - x)
            y_dist += T[j][2]*abs(T[j][1] - y)
        if y_dist <= x_dist:
            XorY[i] = False

    for i in range(N+1):
        ans = 10**18
        for bit in range(1 << N):
            # 選ぶ頂点の個数
            cur = 0
            new_x_road = [0]
            new_y_road = [0]
            for j in range(N):
                if bit & (1 << j):
                    if XorY[j]:
                        new_x_road.append(T[j][0])
                    else:
                        new_y_road.append(T[j][1])
            if i < len(new_x_road) + len(new_y_road) - 2:
                continue
            for x, y, p in T:
                dx = 10**18
                dy = 10**18
                for rx in new_x_road:
                    dx = min(dx, abs(rx-x))
                for ry in new_y_road:
                    dy = min(dy, abs(ry-y))
                cur += p * min(dx, dy)
            ans = min(ans, cur)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = []
for i in range(n):
    x,y,p = map(int,readline().split())
    lst1.append([x,y,p])
made = [(0,0)] #(x=1に引いたならば(1,0)みたいな)

used = [0]*n

def funcx(i):
    res = made + [(lst1[i][0],0)]
    ret = 0
    for i in range(n):
        if used[i]:continue
        loss = 10**18
        for j in range(len(res)):
            x = min(abs(res[j][0]-lst1[i][0]),abs(lst1[i][0]-res[j][0]))
            y = min(abs(res[j][1]-lst1[i][1]),abs(lst1[i][1]-res[j][1]))
            loss = min(loss,lst1[i][2]*min(x,y))
        ret += loss
    return ret

def funcy(i):
    res = made + [(0,lst1[i][1])]
    ret = 0
    for i in range(n):
        if used[i]:continue
        loss = 10**18
        for j in range(len(res)):
            x = min(abs(res[j][0]-lst1[i][0]),abs(lst1[i][0]-res[j][0]))
            y = min(abs(res[j][1]-lst1[i][1]),abs(lst1[i][1]-res[j][1]))
            loss = min(loss,lst1[i][2]*min(x,y))
        ret += loss
    return ret

#初回手動
ret = 0
res = made
for i in range(n):
    loss = 10**18
    for j in range(len(res)):
        x = min(abs(res[j][0]-lst1[i][0]),abs(lst1[i][0]-res[j][0]))
        y = min(abs(res[j][1]-lst1[i][1]),abs(lst1[i][1]-res[j][1]))
        loss = min(loss,lst1[i][2]*min(x,y))
    ret += loss
print(ret)

mura = 0
for i in range(n): #各路線について
    minloss = 10**18
    kouho = (0,0)
    for j in range(n): #各村について
        if not used[j]:
            #x軸アプローチ
            res1 = funcx(j)
            #y軸アプローチ
            res2 = funcy(j)
            if res1<res2:
                if res1 < minloss:
                    minloss = res1
                    kouho = (lst1[j][0],0)
                    mura = j
            else:
                if res2 < minloss:
                    minloss = res2
                    kouho = (0,lst1[j][1])
                    mura = j
    used[mura] = 1
    made.append(kouho)
    print(minloss)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for _ in range(n):
  a.append(list(map(int,input().split())))
ans=sum([min(abs(a[i][0]),abs(a[i][1]))*a[i][2] for i in range(n)])
print(ans)
a.sort(key=lambda x:x[2],reverse=True)
for j in range(n-1):
  print(min(min([sum([min(abs(a[i][0]-a[k][0]),abs(a[i][0]),abs(a[i][1]))*a[i][2] for i in range(n)]) for k in range(j+1)]),min([sum([min(abs(a[i][0]),abs(a[i][1]-a[k][1]),abs(a[i][1]))*a[i][2] for i in range(n)]) for k in range(j+1)])))

Submission status: Wrong Answer

Solution code:
n = int(input())
xyp=[list(map(int,input().split())) for i in range(n)]

from itertools import *

xset=set()
yset=set()
for x,y,p in xyp:
    xset.add(x)
    yset.add(y)

lenx=len(xset)
leny=len(yset)

uniqx=list(xset)
uniqy=list(yset)

uniqx.sort()
uniqy.sort()


for i in range(n+1): # draw i line
    if i>=lenx or i>=leny:
        print(0)
        continue

    ans=10**10
    for tate in range(lenx):
        yoko = i-tate
        if yoko<0:
            continue

        now=0

        for tates in combinations(uniqx,tate):
            for yokos in combinations(uniqy,yoko):
                cur = 0
                for x,y,p in xyp:
                    if x in tates or y in yokos:
                        continue
                    else:
                        mindis = min(abs(x),abs(y))
                        for tmp in tates:
                            mindis=min(mindis,abs(x-tmp))
                        for tmp in yokos:
                            mindis=min(mindis,abs(y-tmp))
                        cur+=mindis*p

                ans=min(ans,cur)

    print(ans)

Submission status: Wrong Answer

Solution code:
# Fast IO (only use in integer input)

# import os,io
# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

minCost = [-1] * (N+1)

totalCases = 3 ** N

for i in range(totalCases):
    railRoad = []
    tmp = i
    for j in range(N):
        railRoad.append(tmp % 3)
        tmp // 3
    numNewRailroad = sum(map(lambda x: 1 if x != 0 else 0,railRoad))
    minDistance = [-1] * N
    for j in range(N):
        minDistance[j] = min(abs(Resident[j][0]),abs(Resident[j][1]))
        for k in range(N):
            if railRoad[k] == 1 and abs(Resident[j][0] - Resident[k][0]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][0] - Resident[k][0])
            if railRoad[k] == 2 and abs(Resident[j][1] - Resident[k][1]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][1] - Resident[k][1])
    cost = 0
    for j in range(N):
        cost += Resident[j][2] + minDistance[j]
    if minCost[numNewRailroad] == -1 or minCost[numNewRailroad] > cost:
        minCost[numNewRailroad] = cost
print('\n'.join(list(map(str,minCost))))

Submission status: Wrong Answer

Solution code:
INF = 10 ** 30
from itertools import combinations
from collections import defaultdict
N = int(input())
XYP = [list(map(int, input().split())) for _ in range(N)]
# X=0,Y=1
origin = [(0, 0), (1, 0)]
XYP.sort(key=lambda x:x[2], reverse=True)
d = defaultdict(int)
X = []
Y = []
all_points = []
for x, y, p in XYP:
    X.append((0,abs(x)))
    Y.append((1,abs(y)))
    d[(0,x)] += p
    d[(1,y)] += p

d = [[i, d[i]] for i in d.keys()]

for i in sorted(d, key=lambda x: x[1], reverse=True):
    all_points.append(i[0])

zerocnt = min(len(set(X)), len(set(Y)))

def calc(cost):
    ret = 0
    for x, y, p in XYP:
        tmp = INF
        for xory, c in cost:
            if xory == 0:
                tmp = min(tmp, abs(c-x) * p)
            else:
                tmp = min(tmp, abs(c-y) * p)
        ret += tmp
    return ret

pre = 0
print(calc(origin))
for i in range(N):
    cost = INF
    for comb in combinations(all_points[:(i+1)*2], i+1):
        comb = list(comb)
        comb.extend(origin)
        cost = min(cost, calc(comb))
    print(cost)
    pre = i

# for i in range(pre+1,N):
#     print(0)

Submission status: Wrong Answer

Solution code:
#Definitely NOT AC

import copy
n=int(input())
p=[]

minx=20000
maxx=-20000
miny=20000
maxy=-20000
for i in range(n):
    xi,yi,pi=map(int,input().split())
    minx=min(minx,xi)
    maxx=max(maxx,xi)
    miny=min(miny,yi)
    maxy=max(maxy,yi)
    p.append((xi,yi,pi))

railway_x={0}
railway_y={0}

INF=10**12
def sum_dist(xs,ys):
    sumi=0
    for i in range(n):
        mini=INF
        for j in xs:mini=min(mini,abs(p[i][0]-j))
        for j in ys:mini=min(mini,abs(p[i][1]-j))
        sumi+=mini*p[i][2]
    return sumi

print(sum_dist(railway_x,railway_y))

for i in range(n):
    tmpx=0
    mini=sum_dist(railway_x,railway_y)
    for j in range(minx,maxx+1):
        tmprailway_x=copy.deepcopy(railway_x)
        tmprailway_x.add(j)
        tmpsum=sum_dist(tmprailway_x,railway_y)
        if mini>tmpsum:
            mini=tmpsum
            tmpx=j
    minix=True
    tmpy=0
    for j in range(miny,maxy+1):
        tmprailway_y=copy.deepcopy(railway_y)
        tmprailway_y.add(j)
        tmpsum=sum_dist(railway_x,tmprailway_y)
        if mini>tmpsum:
            mini=tmpsum
            tmpy=j
            minix=False
    
    if minix:
        railway_x.add(tmpx)
    else:
        railway_y.add(tmpy)
    print(sum_dist(railway_x,railway_y))

Submission status: Wrong Answer

Solution code:
INF = 10 ** 30
from itertools import combinations
from collections import defaultdict
N = int(input())
XYP = [list(map(int, input().split())) for _ in range(N)]
# X=0,Y=1
origin = [(0, 0), (1, 0)]
XYP.sort(key=lambda x:x[2], reverse=True)
d = defaultdict(int)
X = []
Y = []
all_points = []
for x, y, p in XYP:
    X.append((0,abs(x)))
    Y.append((1,abs(y)))
    d[(0,x)] += p
    d[(1,y)] += p

d = [[i, d[i]] for i in d.keys()]

for i in sorted(d, key=lambda x: x[1], reverse=True):
    all_points.append(i[0])

zerocnt = min(len(set(X)), len(set(Y)))

def calc(cost):
    ret = 0
    for x, y, p in XYP:
        tmp = INF
        for xory, c in cost:
            if xory == 0:
                tmp = min(tmp, abs(c-x) * p)
            else:
                tmp = min(tmp, abs(c-y) * p)
        ret += tmp
    return ret

pre = 0
print(calc(origin))
for i in range(N-zerocnt):
    cost = INF
    for comb in combinations(all_points[:(i+1)*2], i+1):
        comb = list(comb)
        comb.extend(origin)
        cost = min(cost, calc(comb))
    print(cost)
    pre = i

for i in range(pre+1,N):
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations
input = sys.stdin.buffer.readline
N = int(input())
cities = []
for _ in range(N):
    X, Y, P = map(int, input().split())
    cities.append((X, Y, P))
# print(f'{cities}')


def f(x0, y0, x1, y1, x2, y2):
    a = x2 - x1
    b = y2 - y1
    a2 = a * a
    b2 = b * b
    r2 = a2 + b2
    tt = -(a * (x1 - x0) + b * (y1 - y0))
    if tt < 0:
        return (x2 - x0) * (x2 - x0) + (y2 - y0) * (y2 - y0)
    f1 = a * (y1 - y0) - b * (x1 - x0)
    return (f1 * f1) / r2


MARGIN = 30000

S = 10**50
for K in range(N):
    gt = combinations(range(N + 2), K)
    for combi in gt:
        do = True
        for i in range(len(combi) - 1):
            for j in range(i + 1, len(combi)):
                if combi[i] + N == combi[j]:
                    do = False
                    break
            if not do:
                break
        if not do:
            continue
        # print(f'{combi=}')
        XY = []
        XY.append((-MARGIN, 0, MARGIN, 0))
        XY.append((0, -MARGIN, 0, MARGIN))
        for i in combi:
            x, y, p = cities[i % N]
            if i < N:
                # yoko
                x1, y1 = x - MARGIN, y
                x2, y2 = x + MARGIN, y
                XY.append((x1, y1, x2, y2))
            else:
                # tate
                x1, y1 = x, y - MARGIN
                x2, y2 = x, y + MARGIN
                XY.append((x1, y1, x2, y2))
        # print(f'{XY=}')

        _S = 0
        for i in range(N):
            x0, y0, p = cities[i]
            d = 10**20
            for x1, y1, x2, y2 in XY:
                d = min(d, f(x0, y0, x1, y1, x2, y2))
            # print(f'd={round(d**0.5)}')
            _S += round(d**0.5) * p
        S = min(S, _S)
        # print(f'{S=}')
    # print(f'for out {S=}')
    print(S)
    if S == 0:
        # print('test')
        for i in range(N - K):
            print(0)
        exit()
print(0)

Submission status: Wrong Answer

Solution code:
import collections

def get_dist(city, direction, c):
    if direction == 0:
        # x軸と平行
        return city[2]*abs(city[1]-c)
    else:
        # y軸と平行
        return city[2]*abs(city[0]-c)

def get_lines(city):
    # 必要な線路の最大本数を求める
    f = [0 for _ in range(n)]
    c = 0

    while f.count(0) != 0:
        x = []
        y = []
        for i in range(n):
            if f[i] == 0:
                x.append(city[i][0])
                y.append(city[i][1])
        c_x = collections.Counter(x)
        c_y = collections.Counter(y)
        if c_x.most_common()[0][1] > c_y.most_common()[0][1]:
            for i in range(n):
                if city[i][0] == c_x.most_common()[0][0]:
                    f[i] = 1
        else:
            for i in range(n):
                if city[i][1] == c_y.most_common()[0][0]:
                    f[i] = 1
        c += 1
    # print(c, 'c')
    return c


n = int(input())
city = [list(map(int, input().split())) for _ in range(n)]
s = 0
for i in range(n):
    x = get_dist(city[i], 0, 0)
    y = get_dist(city[i], 1, 0)
    city[i].append(min(x, y))
    s += min(x, y)
lines = get_lines(city)
print(s)

for k in range(n):
    if k+1 >= lines:
        print(0)
    else:
        div_dist = 0
        direction = 0
        c = 0
        for i in range(n):
            tmp_div_dist = 0
            # x軸平行
            for j in range(n):
                tmp_div_dist += max(city[j][3]-get_dist(city[j], 0, city[i][1]), 0)
            if tmp_div_dist > div_dist:
                div_dist = tmp_div_dist
                direction = 0
                c = city[i][1]
            tmp_div_dist = 0
            # y軸平行
            for j in range(n):
                tmp_div_dist += max(city[j][3]-get_dist(city[j], 1, city[i][0]), 0)
            if tmp_div_dist > div_dist:
                div_dist = tmp_div_dist
                direction = 1
                c = city[i][0]

        s = 0
        for i in range(n):
            city[i][3] = min(city[i][3], get_dist(city[i], direction, c))
            s += city[i][3]
        print(s)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from itertools import combinations
input = sys.stdin.buffer.readline
N = int(input())
cities = []
for _ in range(N):
    X, Y, P = map(int, input().split())
    cities.append((X, Y, P))


def f(x0, y0, x1, y1, x2, y2):
    a = x2 - x1
    b = y2 - y1
    a2 = a * a
    b2 = b * b
    r2 = a2 + b2
    tt = -(a * (x1 - x0) + b * (y1 - y0))
    if tt < 0:
        return (x2 - x0) * (x2 - x0) + (y2 - y0) * (y2 - y0)
    f1 = a * (y1 - y0) - b * (x1 - x0)
    return (f1 * f1) / r2


# d = f(0, 4, -1000, 0, 5, 0)
# print(f'{d=}')

MARGIN = 30000

# print(f'{cities}')

S = 10**50
for K in range(N):
    gt = combinations(range(N + 2), K)
    for combi in gt:
        do = True
        for i in range(len(combi) - 1):
            for j in range(i + 1, len(combi)):
                if combi[i] + N == combi[j]:
                    do = False
                    break
            if not do:
                break
        if not do:
            continue
        # print(f'{combi=}')
        XY = []
        XY.append((-MARGIN, 0, MARGIN, 0))
        XY.append((0, -MARGIN, 0, MARGIN))
        for i in combi:
            x, y, p = cities[i % N]
            if i < N:
                # yoko
                x1, y1 = x - MARGIN, y
                x2, y2 = x + MARGIN, y
                XY.append((x1, y1, x2, y2))
            else:
                # tate
                x1, y1 = x, y - MARGIN
                x2, y2 = x, y + MARGIN
                XY.append((x1, y1, x2, y2))
        # print(f'{XY=}')

        _S = 0
        for i in range(N):
            x0, y0, p = cities[i]
            d = 10**20
            for x1, y1, x2, y2 in XY:
                d = min(d, f(x0, y0, x1, y1, x2, y2))
            # print(f'd={round(d**0.5)}')
            _S += round(d**0.5) * p
        S = min(S, _S)
        # print(f'{S=}')
    # print(f'for out {S=}')
    print(S)
    if S == 0:
        # print('test')
        for i in range(N - K):
            print(0)
        exit()
print(0)

Submission status: Wrong Answer

Solution code:
import copy

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
total_dists = []
for x, y, p in XYP:
    total_dists.append(p * min(x, y))

xypd = [[*t, d] for t, d in zip(XYP, total_dists)]
xypd.sort(reverse=True, key=lambda t: t[-1])
for k in range(N + 1):
    ns_lines, ew_lines = {0}, {0}
    i = 0
    while i < k:
        if i >= N:
            break

        if xypd[i][0] not in ns_lines:
            ns_lines.add(xypd[i][0])
            td_ns = 0
            for x, y, p, d in xypd:
                td_ns += p * min(*(abs(x - ns) for ns in ns_lines), *(abs(y - ew) for ew in ew_lines))
            ns_lines.remove(xypd[i][0])
        else:
            td_ns = 10**10

        if xypd[i][1] not in ew_lines:
            ew_lines.add(xypd[i][1])
            td_ew = 0
            for x, y, p, d in xypd:
                td_ew += p * min(*(abs(x - ns) for ns in ns_lines), *(abs(y - ew) for ew in ew_lines))
            ew_lines.remove(xypd[i][1])
        else:
            td_ew = 10 ** 10

        if td_ns == 10 ** 10 and td_ew == 10 ** 10:
            k += 1
        elif td_ns < td_ew:
            ns_lines.add(xypd[i][0])
        else:
            ew_lines.add(xypd[i][1])

        i += 1

    td = 0
    for x, y, p, d in xypd:
        td += p * min(*(abs(x - ns) for ns in ns_lines), *(abs(y - ew) for ew in ew_lines))
    print(td)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

def get_cands(cost, axis):
    cands = set()
    for i in range(N):
        if cost[i] != 0:
            cands.add(axis[i])
    return cands

def update_cost(cost, x, axis):
    cost = list(cost)
    for i in range(N):
        cost[i] = min(cost[i], P[i] * abs(axis[i]-x))
    return tuple(cost)

cost = tuple([P[i] * min(abs(X[i]), abs(Y[i])) for i in range(N)])
print(sum(cost))
costs =[ cost]

for k in range(N):
    new_costs = set()
    for cost in costs:
        for axis in X, Y:
            best_cost = tuple([0]*N)
            best_score = 0
            for cand in get_cands(cost, axis):
                new_cost = update_cost(cost, cand, axis)
                score = sum(new_cost)
                if score > best_score:
                    best_cost = new_cost
                    best_score = score
            new_costs.add(tuple(best_cost))

    costs = new_costs
    if not costs:
        print(0)
    else:
        print(min([sum(cost) for cost in costs]))

Submission status: Wrong Answer

Solution code:
def distance(xr, yr, x, y, p):
    x_ditance = min(list(map(lambda a: abs(a - x), xr)))
    y_ditance = min(list(map(lambda a: abs(a - y), yr)))
    return min([x_ditance,y_ditance]) * p


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

for K in range(N):
    x_route = [0]
    y_route = [0]
    sum = 0
    for i in range(K):
        max_city_index = P.index(max(P))
        pattern_x = 0
        for i in range(N):
            pattern_x += distance(x_route + [X[max_city_index]], y_route, X[i], Y[i], P[i])
        pattern_y = 0
        for i in range(N):
            pattern_y += distance(x_route , y_route + [Y[max_city_index]], X[i], Y[i], P[i])
        if(pattern_x > pattern_y):
            y_route += [Y[max_city_index]]
        else:
            x_route += [X[max_city_index]]
        P[max_city_index] = 0
    for i in range(N):
        sum += distance(x_route, y_route, X[i], Y[i], P[i])
    print(sum)

Submission status: Wrong Answer

Solution code:
import itertools

G = []
MAX = 10 ** 9 + 1

def calcS(R_x, R_y):
    S = 0
    for g in G:
        near_r = MAX
        x,y,p = g
        for r in R_x:
            if near_r == 0:
                break
            near_r = min(near_r, abs(x-r))
        for r in R_y:
            if near_r == 0:
                break
            near_r = min(near_r, abs(y-r))
        S += p * near_r
    return S

def resolve():
    global G

    n = int(input())
    G = []

    # 道路の建設予定地
    pre_x = set()
    pre_y = set()
    # pre[i] = [x or y, index]
    pre = []

    for _ in range(n):
        x,y,p = list(map(int, input().split()))
        if x not in pre_x:
            pre_x.add(x)
            pre.append(["x", x])
        if y not in pre_y:
            pre_y.add(y)
            pre.append(["y", y])
        G.append([x,y,p])


    for i in range(n+1):
        if i == 0:
            print(calcS([0], [0]))
            continue

        min_S = MAX
        # i本通路を建設する
        for R in itertools.combinations(pre, i):
            R_x = [0]
            R_y = [0]
            for r in R:
                if r[0] == "x":
                    R_x.append(r[1])
                else:
                    R_y.append(r[1])
            min_S = min(min_S, calcS(R_x, R_y))
        
        print(min_S)
    
resolve()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations_with_replacement,product
import numpy as np
def input(): return sys.stdin.readline().rstrip()
def kyori(xlist,ylist,x,y):
    return min(np.min(np.abs(np.array(xlist)-x)),np.min(np.abs(np.array(ylist)-y)))

 
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)
    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 itertools as it
import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def array(size, init=0):
    return [[init for j in range(size[1])] for i in range(size[0])]


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())


directions = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def permutate(x, A):
    n = len(x)
    res = [-1]*n
    for i in range(n):

        res[i] = x[A[i]]
    return res


def generate_bin(digit):
    for b in range(2**digit):
        b = bin(b)
        tmp = b[2:].zfill(digit)
        yield list(map(int, tmp))
        # b=list(map(int,list(b[2:].zfill(digit))))
        # yield b


def search(x, count):
    #print("top", x, count)

    for d in directions:
        nx = d+x
        # print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)

    return count


N = int(input())

shuraku = []
for i in range(N):
    shuraku.append(acinput())

for k in range(0, N+1):
    mincost = 10**9
    #print("k", k)
    for sc in it.combinations(range(0, N), k):
        #print("sc", sc)
        for l in generate_bin(k):
            xx = [0]
            yy = [0]
            # print(l)
            m = 0
            for ssc in sc:
                if l[m] == 0:
                    xx.append(shuraku[ssc][0])
                else:
                    yy.append(shuraku[ssc][1])
                m += 1

            #print("xx", xx, yy)
            cost = 0
            for ss in shuraku:
                tmpx = np.abs(np.array(xx)-ss[0])
                tmpy = np.abs(np.array(yy)-ss[1])
                tmp = min(min(tmpx), min(tmpy))
                cost += tmp*ss[2]

            mincost = min(cost, mincost)

    print(mincost)