Problem:


Score: 500 points

Problem Statement

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

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

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

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

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

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

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

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

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

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

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

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

Constraints

1 \leq N \leq 15

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

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

1 \leq P_i \leq 1 \ 000 \ 000

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer in N+1 lines.

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

Sample Input 1

3
1 2 300
3 3 600
1 4 800

Sample Output 1

2900
900
0
0

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

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

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

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

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

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

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

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

Sample Input 2

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

Sample Output 2

13800
1600
0
0
0
0

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

Sample Input 3

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

Sample Output 3

26700
13900
3200
1200
0
0
0

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

Sample Input 4

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

Sample Output 4

2576709
1569381
868031
605676
366338
141903
0
0
0

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



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


Sample output:
2900
900
0
0

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from itertools import combinations
from collections import defaultdict

def main():
	n=II()
	dx=[defaultdict(lambda:-1) for _ in range(n)]
	dy=[defaultdict(lambda:-1) for _ in range(n)]
	X=[]
	Y=[]
	P=[]
	for _ in range(n):
		x,y,p=MI()
		X.append(x)
		Y.append(y)
		P.append(p)
	#print(X,Y,P)

	for i in range(n):
		aans=10**15
		a=combinations(range(n),i)
		for li in list(a):
			#print(li)
			for j in range(1<<i):
				x=[0]
				y=[0]
				for k in range(i):
					if j&1<<k:
						x.append(X[li[k]])
					else:
						y.append(Y[li[k]])
				#print(i,j,k)
				#print(x,y)
				x=tuple(x)
				y=tuple(y)

				ans=0
				for ii in range(n):
					d=10**6
					if dx[ii][x]!=-1:
						d=min(d,dx[ii][x])
					else:
						dxx=10**6
						for xx in x:
							dxx=min(dxx,abs(X[ii]-xx))
						dx[ii][x]=dxx
						d=min(d,dxx)
					if dy[ii][y]!=-1:
						d=min(d,dy[ii][y])
					else:
						dyy=10**6
						for yy in y:
							dyy=min(dyy,abs(Y[ii]-yy))
						dy[ii][y]=dyy
						d=min(d,dyy)
					ans+=P[ii]*d
				aans=min(aans,ans)
		print(aans)
	print(0)













































if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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)

preCalRange = 1 << N

horizontalLineDistance = []
verticalLineDistance = []

for i in range(preCalRange):
    railRoad = []
    tmp = i
    for j in range(N):
        railRoad.append(tmp % 2)
        tmp //= 2
    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])
    horizontalLineDistance.append(tuple(minDistance))
    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][1] - Resident[k][1]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][1] - Resident[k][1])
    verticalLineDistance.append(tuple(minDistance))

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))
    horizontalCount = 0
    verticalCount = 0
    for j in range(N):
        if railRoad[j] == 1:
            horizontalCount += 1 << j
        if railRoad[j] == 2:
            verticalCount += 1 << j
    minDistance = [-1] * N
    for j in range(N):
        minDistance[j] = min(horizontalLineDistance[horizontalCount][j], verticalLineDistance[verticalCount][j])

    cost = 0
    for j in range(N):
        cost += Resident[j][2] * minDistance[j]
    if minCost[numNewRailroad] == -1 or minCost[numNewRailroad] > cost:
        minCost[numNewRailroad] = cost
for elem in minCost:
    print(elem)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import bisect


def solve():
    N = int(input())
    villages = [tuple(map(int, input().split())) for _ in range(N)]

    ans = [float('inf')] * (N + 1)
    for t in itertools.product(range(3), repeat=N):
        ct = N - t.count(0)
        X = sorted([x for i, (x, _, _) in enumerate(villages) if t[i] == 1])
        Y = sorted([y for i, (_, y, _) in enumerate(villages) if t[i] == 2])
        dist = [0] * N

        if X:
            for i, (x, _, _) in enumerate(villages):
                bx = bisect.bisect_left(X, x)
                if bx == 0:
                    dist[i] = min(abs(x), X[0] - x)
                elif bx == len(X):
                    dist[i] = min(abs(x), x - X[-1])
                else:
                    dist[i] = min(abs(x), x - X[bx - 1], X[bx] - x)
        else:
            for i, (x, _, _) in enumerate(villages):
                dist[i] = abs(x)
        if Y:
            for i, (_, y, _) in enumerate(villages):
                by = bisect.bisect_left(Y, y)
                if by == 0:
                    dist[i] = min(dist[i], abs(y), Y[0] - y)
                elif by == len(Y):
                    dist[i] = min(dist[i], abs(y), y - Y[-1])
                else:
                    dist[i] = min(dist[i], abs(y), y - Y[by - 1], Y[by] - y)
        else:
            for i, (_, y, _) in enumerate(villages):
                dist[i] = min(dist[i], abs(y))

        ans[ct] = min(ans[ct], sum(dist[i] * villages[i][2] for i in range(N)))
    print(*ans, sep='\n')


solve()

Submission status: Time Limit Exceeded

Solution code:
#E
import math
import itertools

N = int(input())

X= []
Y= []
P= []

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

def calc_S_single(x, y, p, x_lines, y_lines):
    cost_x = [math.fabs(x1-x) for x1 in x_lines]
    cost_y = [math.fabs(y1-y) for y1 in y_lines]
    cost = cost_x + cost_y
    cost_min = min(cost)
    return p*cost_min

def search_K(N,
           X,
           Y,
           P,
           X_line,
           Y_line,
           x=[],
           y=[]):
    X_line2 = X_line+x
    Y_line2 = Y_line+y
    
    total_cost = 0
    for x,y,p in zip(X, Y, P):
        total_cost += calc_S_single(x,y,p,
                                   X_line2,
                                   Y_line2)
    
    return total_cost

class CostMng():
    def __init__(self):
        self.inv_cost = 0
        self.cost = 0
# cost S

X_line = [0]
Y_line = [0]

res = search_K(N,
               X,
               Y,
               P,
               X_line,
               Y_line,
               x=[],
               y=[])

print(int(res))

X2 = ["x"+str(x) for x in X]
Y2 = ["y"+str(y) for y in Y]
XY = list(set(X2 + Y2))

for i in range(1, N+1):
    combo = itertools.combinations(XY, i)
    
    #print(X[i], Y[i], P[i])
    cost_mng = CostMng()
    
    for c2 in combo:
        xc = []
        yc = []
        for c in c2:
            if c[0]=="x":
                xc += [int(c[1:])]
            if c[0]=="y":
                yc += [int(c[1:])]
        
        #print(xc,yc)

        res = search_K(N,
                       X,
                       Y,
                       P,
                       X_line,
                       Y_line,
                       x=xc,
                       y=yc)
        #print(res)

        inv_cost = 10000./(1+res)
        if cost_mng.inv_cost < inv_cost:
            cost_mng.inv_cost = inv_cost
            cost_mng.cost = res
        
        #print(kx, res)
    
    #print()
    #print("res")
    print(int(cost_mng.cost))
    #print()

Submission status: Time Limit Exceeded

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()
    lis = [[[0],0],[[1],1],[[2],1]]
    for _ in range(n-1):
        lis = [[x[0]+[i],x[1]+(i>0)] for i in range(3) for x in lis if x[1] < n-2]
    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 l,cnt in lis:
        lx = []
        ly = []
        if ans[cnt] <= 0:
            continue
        for i in range(n):
            li = l[i]
            x,y = p[i][:2]
            if li == 1:
                lx.append(x)
            elif li == 2:
                ly.append(y)
        ly.sort()
        s = 0
        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[cnt]:
            ans[cnt] = s
    for i in ans:
        print(i)
    return

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import bisect

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

ans = []

def calc(x,y,i):
    tmp = 10**10
    xi,yi = xyp[i][:2]
    x_ind = bisect.bisect_left(x,xi)
    y_ind = bisect.bisect_left(y,yi)
    if(x_ind==0):
        tmp = min(tmp, x[0]-xi)
    elif(x_ind==len(x)):
        tmp = min(tmp, xi - x[x_ind-1])
    else:
        tmp = min(tmp, x[x_ind]-xi)
        tmp = min(tmp, xi - x[x_ind-1])

    if(y_ind==0):
        tmp = min(tmp, y[0]-yi)
    elif(y_ind==len(y)):
        tmp = min(tmp, yi - y[y_ind-1])
    else:
        tmp = min(tmp, y[y_ind]-yi)
        tmp = min(tmp, yi - y[y_ind-1])
    # print(x)
    # print(y)
    # print(i,xi,yi,tmp*xyp[i][2])
    # print('')

    return tmp* xyp[i][2]

tmp = 0
for i in range(n):
    tmp += calc([0],[0],i)
ans.append(tmp)

for i in range(1,n+1):
    tmp = 10**10
    for c in itertools.combinations(range(n), i):
        d = []
        for j in range(n):
            if(not j in c):
                d.append(j)
        for j in range(2**i):
            x = [0]
            y = [0]
            tmp2 = 0
            for k in range(i):
                if(j>>k)&1:
                    y.append(xyp[c[k]][1])
                else:
                    x.append(xyp[c[k]][0])
            x.sort()
            y.sort()
            for k in d:
                tmp2 += calc(x,y,k)
            tmp = min(tmp,tmp2)
    ans.append(tmp)

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

Submission status: Time Limit Exceeded

Solution code:
def score(CITIES, lines):
    s = 0
    for c in CITIES:
        x = c[0]
        y = c[1]
        p = c[2]

        min_dist = 1000000000000
        for l in lines:
            if l[1] == "H":
                dist = abs(y-l[0])
            else:
                dist = abs(x-l[0])
            min_dist = min(min_dist, dist)
        s += min_dist * p
    return s

def recursive_score(K, CITIES, candidate_lines, selected, max_selected):
    if K == len(CITIES):
        return 0

    if len(selected) == K:
        lines = [[0, "H"], [0, "V"]]
        for s in selected:
            lines.append(candidate_lines[s])
        return score(CITIES, lines)

    min_score = 1000000000000
    for i in range(len(candidate_lines)):
        if i <= max_selected:
            continue
        max_selected = i
        sel = selected + [i]
        s = recursive_score(K, CITIES, candidate_lines, sel, max_selected)
        if s == 0:
            return 0
        min_score = min(min_score, s)
    return min_score

def main():
    N = int(input())
    CITIES = []

    for i in range(N):
        # x=c[0]
        # y=c[1]
        # p=c[2]
        c = [int(_x) for _x in input().split()]
        CITIES.append(c)

    candidate_lines_org = []
    for i in range(N):
        candidate_lines_org.append([CITIES[i][1], "H"])  # y座標が同じで横線
        candidate_lines_org.append([CITIES[i][0], "V"])  # x座標が同じで縦線

    # 2つ以上の都市に乗る線は優先度を高くしつつ、一回のみカウント
    duplicate_lines = []
    single_lines = []
    for i in range(len(candidate_lines_org)):
        dup = False
        for j in range(len(candidate_lines_org)):
            if j <= i:
                continue
            if candidate_lines_org[i] == candidate_lines_org[j]:
                dup = True
                duplicate_lines.append(candidate_lines_org[i])
                break
        if not dup:
            single_lines.append(candidate_lines_org[i])
    candidate_lines = duplicate_lines + single_lines

    for K in range(N+1):
        S = recursive_score(K, CITIES, candidate_lines, [], -1)
        print(S)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(n)]

    horizon = [[INF] * (1 << n) for _ in range(n)]
    vertical = [[INF] * (1 << n) for _ in range(n)]
    for i in range(n):
        x0, y0, p0 = XYP[i]
        for U in range(1 << n):
            hor = abs(x0) * p0
            ver = abs(y0) * p0
            for j in range(n):
                if not (U >> j & 1):
                    continue
                x1, y1, p1 = XYP[j]
                hor = min(hor, abs(x1 - x0) * p0)
                ver = min(ver, abs(y1 - y0) * p0)
            horizon[i][U] = hor
            vertical[i][U] = ver

    ans = [INF] * (n + 1)
    for U in range(1 << n):
        k = bin(U).count('1')
        ans[k] = min(ans[k], sum(min(horizon[i][0], vertical[i][U]) for i in range(n)))
        V = U
        while V:
            W = U ^ V
            ans[k] = min(ans[k], sum(min(horizon[i][V], vertical[i][W]) for i in range(n)))
            V = (V - 1) & U

    print(*ans, sep = '\n')
resolve()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

for i in range(2**N):
    X=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            X.append(city[j][0])
            xx[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in X:
            res=min(res,abs(city[j][0]-k))
        xx[i][j]=res

for i in range(2**N):
    Y=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            Y.append(city[j][1])
            yy[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in Y:
            res=min(res,abs(city[j][1]-k))
        yy[i][j]=res

ans=[10**15 for i in range(N+1)]
for i in range(3**N):
    rest=i
    X=0
    Y=0
    count=0
    amari=[]
    for j in range(N):
        r=rest%3
        if r==1:
            count+=1
            X+=2**j
        elif r==2:
            count+=1
            Y+=2**j
        else:
            amari.append(j)
        rest//=3
    res=0
    for j in amari:
        x=xx[X][j]
        y=yy[Y][j]
        res+=min(x,y)*city[j][2]
    ans[count]=min(ans[count],res)

for i in range(N+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from bisect import bisect_left


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



def solve(N, XYP, INF=1<<61):
    # 3^N通り全て試す
    # 東西、左右、道なしの3通り
    minK = [INF for i in range(N+1)]

    for ptn in product(range(3), repeat=N):
        nh = ptn.count(1)
        nv = ptn.count(2)
        k = nh + nv
        # calculate score
        score = 0
        nearest_x = [abs(x)*p for x, y, p in XYP]
        nearest_y = [abs(y)*p for x, y, p in XYP]
        for i in range(N):
            x, y, p = XYP[i]
            for j in range(N):
                x1, y1, p1 = XYP[j]
                if ptn[j] == 1:
                    nearest_x[i] = min(nearest_x[i], abs(x - x1)*p)
                elif ptn[j] == 2:
                    nearest_y[i] = min(nearest_y[i], abs(y -y1) * p)
                
        for i in range(N):
            score += min(nearest_x[i], nearest_y[i])
        minK[k] = min(minK[k], score)
    
    for k in range(0, N+1):
        print(minK[k])
    


if __name__ == '__main__':
    inputs = read()
    solve(*inputs)

Submission status: Time Limit Exceeded

Solution code:
# Kこの街について，それぞれ横に串刺しにするか縦に串刺しにするかを選んでDFS
N = int(input())

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

def dfs(XL,YL,PL,K):
    # もう残りのやつがなかったら，０になる
    if not PL:
        return 0
    # 残りがあるけど，全部線を引き終えたら，残りのポイントたちについて距離を計算
    if len(XL)+len(YL)==K+2:
        score = 0
        for x,y,p in PL:
            x_dis = min([abs(x-xl) for xl in XL])
            y_dis = min([abs(y-yl) for yl in YL])
            min_dis = min(x_dis,y_dis)
            score += min_dis*p

        return score
    # それ以外のときは線を引いていく
    score = []
    for i, pl in enumerate(PL):
        x,y,_ = pl
        x = [x]
        y = [y]
        new_score = (min(dfs(XL+x,YL,PL[:i]+PL[i+1:],K),dfs(XL,YL+y,PL[:i]+PL[i+1:],K)))
        score.append(new_score)
        if new_score == 0:
            break

    return min(score)

ans = -1
for i in range(N+1):
    if ans == 0:
        print(0)
        continue
    ans = dfs([0],[0],L,i)
    print(ans)

Submission status: Time Limit Exceeded

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


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    P = read_lists(N)

    C = [V(min) for _ in range(N + 1)]
    for T in itertools.product(range(3), repeat=N):
        X = {0}
        Y = {0}
        S = set()
        for i, t in enumerate(T):
            if t == 1:
                X.add(P[i][0])
                S.add(i)
            elif t == 2:
                Y.add(P[i][1])
                S.add(i)

        c = 0
        for j, (xp, yp, p) in enumerate(P):
            if j in S:
                continue
            cx = min(abs(xp - x) for x in X)
            cy = min(abs(yp - y) for y in Y)
            c += min(cx, cy) * p
        C[len(X) + len(Y) - 2].ud(c)

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
import itertools
n=int(input())
towns=[]
for i in range(n):
  x,y,p=map(int,input().split())
  towns.append([x,y,p])
ans=0
for i in range(n):
  ans+=min(abs(towns[i][0]),abs(towns[i][1]))*towns[i][2]
print(ans)
hor=[]
vert=[]
for i in range(n):
  hor.append([])
  vert.append([])
P=[]
for i in range(n):
  P.append(i)
for i in range(n):
  for j in itertools.combinations(P, i):
    hor[i].append([])
    for l in range(n):
      d=towns[l][1]
      mx=abs(d)
      for t in j:
        mx=min(mx,abs(towns[t][1]-d))
      hor[i][-1].append(mx)
for i in range(n):
  for j in itertools.combinations(P, i):
    vert[i].append([])
    for l in range(n):
      d=towns[l][0]
      mx=abs(d)
      for t in j:
        mx=min(mx,abs(towns[t][0]-d))
      vert[i][-1].append(mx)

for i in range(1,n):
  minans=-1
  for j in range(i+1):
    for k in hor[j]:
      for l in vert[i-j]:
        ans=0
        for m in range(n):
          ans+=towns[m][2]*min(k[m],l[m])
        if minans==-1:
          minans=ans
        else:
          minans=min(ans,minans)
  print(minans)
          
print(0)

Submission status: Time Limit Exceeded

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


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    P = read_lists(N)

    C = [V(min) for _ in range(N + 1)]
    for T in itertools.product(range(3), repeat=N):
        X = {0}
        Y = {0}
        for i, t in enumerate(T):
            if t == 1:
                X.add(P[i][0])
            elif t == 2:
                Y.add(P[i][1])

        c = 0
        for xp, yp, p in P:
            cx = min(abs(xp - x) for x in X)
            cy = min(abs(yp - y) for y in Y)
            c += min(cx, cy) * p
        C[len(X) + len(Y) - 2].ud(c)

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
XYP = [list(map(int, input().split())) for i in range(N)]
x_min = min(x for x, _, _ in XYP)
x_max = max(x for x, _, _ in XYP)
y_min = min(y for _, y, _ in XYP)
y_max = max(y for _, y, _ in XYP)

Lines = {(0, None), (None, 0)}
c_lines = {(x, None) for x in range(x_min, x_max + 1)} \
    | {(None, y) for y in range(y_min, y_max + 1)} \
    - Lines


def calc_distance(xyp, line):
    lx, ly = line
    x, y, p = xyp
    if lx is None:
        return abs(y - ly) * p
    if ly is None:
        return abs(x - lx) * p
    return min(abs(x - lx), abs(y - ly)) * p


def calc_s(lines):
    d = []
    for xyp in XYP:
        d.append(min(calc_distance(xyp, line) for line in lines))
    return sum(d)


zero = False
for k in range(N + 1):
    if zero:
        print(0)
        continue
    s = []
    for item in itertools.combinations(c_lines, k):
        t_lines = set(item) | Lines
        s.append(calc_s(t_lines))
    print(min(s))
    if min(s) == 0:
        zero = True

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13

if n > 15:
    print(re)
    
costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))


x_dir = [[INF] * (1 << n) for i in range(n)]
y_dir = [[INF] * (1 << n) for i in range(n)]

for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[i][bit_state] = min(costs[i], x_dir[i][bit_state])
        y_dir[i][bit_state] = min(costs[i], y_dir[i][bit_state])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[j][bit_state] = min(x_dir[j][bit_state], c * abs(yi - yj))
            y_dir[j][bit_state] = min(y_dir[j][bit_state], c * abs(xi - xj))


ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[i][x_bit], y_dir[i][y_bit])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

ans[-1] = 0
for res in ans:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
# Kこの街について，それぞれ横に串刺しにするか縦に串刺しにするかを選んでDFS
N = int(input())

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

def dfs(XL,YL,PL,K):
    # もう残りのやつがなかったら，０になる
    if not PL:
        return 0
    # 残りがあるけど，全部線を引き終えたら，残りのポイントたちについて距離を計算
    if len(XL)+len(YL)==K+2:
        score = 0
        for x,y,p in PL:
            x_dis = min([abs(x-xl) for xl in XL])
            y_dis = min([abs(y-yl) for yl in YL])
            min_dis = min(x_dis,y_dis)
            score += min_dis*p

        return score
    # それ以外のときは線を引いていく
    score = []
    for i, pl in enumerate(PL):
        x,y,_ = pl
        x = [x]
        y = [y]
        score.append(min(dfs(XL+x,YL,PL[:i]+PL[i+1:],K),dfs(XL,YL+y,PL[:i]+PL[i+1:],K)))
    return min(score)


for i in range(N+1):
    print((dfs([0],[0],L,i)))

Submission status: Time Limit Exceeded

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

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

for bit in range(1 << n):
    k = (bit & 0x5555) + (bit >> 1 & 0x5555)
    k = (k & 0x3333) + (k >> 2 & 0x3333)
    k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
    k = (k & 0x00ff) + (k >> 8 & 0x00ff)
    i = 0
    t = bit
    selected = []
    while t:
        if t & 1:
            selected.append(towns[i])
        t >>= 1
        i += 1

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

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