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

def main():
	n=II()
	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)

				ans=0
				for ii in range(n):
					d=10**6
					for xx in x:
						d=min(d,abs(X[ii]-xx))
					for yy in y:
						d=min(d,abs(Y[ii]-yy))
					ans+=P[ii]*d
				aans=min(aans,ans)
		print(aans)
	print(0)













































if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n = int(input())

init_score = 0
xy = []
mind = []
Ps = []
for i in range(n):
    x, y, p = map(int, input().split())
    xy.append((x, y))
    Ps.append(p)
    mind.append(min(abs(x), abs(y)))
    init_score += mind[i]*p

print(init_score)

# k本選ぶ
# 30Ck
skip = 0
for k in range(1, n+1):
    if skip:
        print(0)
        continue
    max_imp = 0
    for subset in combinations(range(2*n), k):
        # print(subset)
        nmind = mind.copy()
        for v in subset:
            a, b = divmod(v, 2)
            if b == 0:
                x, _ = xy[a]
                for i in range(n):
                    x2, _ = xy[i]
                    new_d = abs(x2-x)
                    if new_d < nmind[i]:
                        nmind[i] = new_d
            else:
                _, y = xy[a]
                for i in range(n):
                    _, y2 = xy[i]
                    new_d = abs(y2-y)
                    if new_d < mind[i]:
                        nmind[i] = new_d

        def calc(ls):
            return sum(abs(x-y)*Ps[i] for i, (x, y) in enumerate(zip(mind, nmind)))
        improve = calc(nmind)
        if max_imp < improve:
            max_imp = improve
    score = init_score-max_imp
    print(score)
    if score == 0:
        skip = 1

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
X = []
Y = []
P = []
for i in range(N):
    x, y, p = map(int, input().split())
    X += [x]
    Y += [y]
    P += [p]
base_list = [i for i in range(N)]
# base_cost = [min(abs(x), abs(y)) * p for x, y, p in zip(X, Y, P)]
base_cost = [min(abs(x), abs(y)) for x, y in zip(X, Y)]

# print(base_cost)
for k in range(0, N+1):
    ans = sum([d*p for d, p in zip(base_cost, P)])
    comb_gen = itertools.combinations(base_list, k)
    for comb in comb_gen:
        for b in range(2**k):
            cost = base_cost.copy()
            for ci in comb:
                if b & 1:
                    for i in range(N):
                        cost[i] = min(abs(Y[ci]-Y[i]), cost[i])
                else:
                    for i in range(N):
                        cost[i] = min(abs(X[ci]-X[i]), cost[i])
                b = b >> 1
            ans = min(ans, sum([d*p for d, p in zip(cost, P)]))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right, insort_left, insort_right
from functools import reduce

N = a_int()
XYP = read_tuple(N)
X, Y, P = zip(*XYP)
# i=0,1のときは簡単
# i=>2のときにどうするか...
# まてよ、各点について、[なし、縦、横]の三種類の全探索なら3^15=14348907でぎり間に合う
# それで何本鉄道路線を敷いたかのdictに突っ込んであげれば良い
# なかのループも考えると10^9ぐらいになってCppじゃないと間に合わんなぁ

ans = defaultdict(lambda: 10**15 + 1)

for types in product(range(3), repeat=N):
    n_rails = 0
    Xs = []  # 縦のrails #単調増加
    Ys = []  # 縦のrails #単調増加
    i_walk = []  # 歩くのが必要な集落のidx
    for i, ty in enu(types):
        if ty == 0:  # railsをしかない
            i_walk.append(i)
        elif ty == 1:  # railsを縦に敷く
            Xs.append(X[i])
            n_rails += 1
        else:  # railを横にしく
            Ys.append(Y[i])
            n_rails += 1
    Xs.append(10**9)
    Ys.append(10**9)
    insort_left(Xs, 0)
    insort_left(Ys, 0)
    # 歩くコストの計算
    cost = 0
    for i in i_walk:
        # Xの一番路線
        idx = bisect_left(Xs, X[i])
        d_x = min(abs(Xs[idx] - X[i]), abs(Xs[idx - 1] - X[i]))
        # Yの一番近い路線
        idx = bisect_left(Ys, Y[i])
        # print(idx, Ys, Y)
        d_y = min(abs(Ys[idx] - Y[i]), abs(Ys[idx - 1] - Y[i]))
        cost += min(d_x, d_y) * P[i]

    ans[n_rails] = min(ans[n_rails], cost)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N = int(input())

XYP = []
x = set()
y = set()
for _ in range(N):
    X, Y, P = map(int, input().split())
    if X == 0 or Y == 0:
        continue
    x.add(X)
    y.add(Y)
    XYP.append((X, Y, P))

S = float('inf')
for K in range(N + 1):
    if S != 0:
        S = float('inf')
        for k in range(K + 1):
            for cx in combinations(x, k):
                xx = [0] + list(cx)
                for cy in combinations(y, K - k):
                    yy = [0] + list(cy)
                    t = 0
                    for X, Y, P in XYP:
                        m = float('inf')
                        for i in xx:
                            m = min(m, abs(X - i))
                        for i in yy:
                            m = min(m, abs(Y - i))
                        t += m * P
                    S = min(S, t)
        print(S)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
cities = []
S = 0
candx = []
candy = []
for _ in range(N):
    city = [int(i) for i in input().split()]
    candx.append(city[0])
    candy.append(city[1])
    cities.append(city)
    S += city[2]*min(abs(city[0]),abs(city[1]))
print(S)
for i in range(1,N):
    a = 0
    for j in range(i+1):
        for x in itertools.combinations(candx,j):
            for y in itertools.combinations(candy,i-j):
                draft = 0
                x = list(x)
                y = list(y)
                for city in cities:
                    dx = float("inf")
                    dy = float("inf")
                    if x:
                        dx = min([abs(city[0]-k) for k in x])
                    if y:
                        dy = min([abs(city[1]-k) for k in y])
                    draft += city[2]*(min(abs(city[0]),abs(city[1])) - min(abs(city[0]),abs(city[1]),dx,dy))
                a = max(a,draft)
    print(S-a)
    if S == a:
        for _ in range(N-i-1):
            print(0)
        break
print(0)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())

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

for i in range(n+1):
    rett = 1e18
    rs = []
    for comb in itertools.combinations(range(n),i):
        for bits in itertools.product([0,1],repeat=i):
            temp = []
            for j in range(i):
                if bits[j] == 0:
                    temp.append([v[comb[j]][0],0])
                else:
                    temp.append([0,v[comb[j]][1]])
            rs.append(temp)


    for roads in rs:
        temp = 0
        for j in range(n):
            mroad = min(abs(v[j][0]),abs(v[j][1]))
            for road in roads:
                dx = abs(road[0]-v[j][0])
                dy = abs(road[1]-v[j][1])
                dd = min(dx,dy)
                mroad = min(mroad,dd)
            temp += mroad*v[j][2]

        if temp < rett:
            rett = temp
    print(rett)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def main(XYP):
    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
    N = len(X)
    dp = np.empty((3**N, N), np.int64)  # 建設、人 -> コスト
    dp[0] = np.minimum(np.abs(X), np.abs(Y))
    size = np.empty(3**N, np.int64)
    size[0] = 0
    for n in range(N):
        B = 3**n
        DX = np.abs(X - X[n])
        DY = np.abs(Y - Y[n])
        for s in range(B):
            dp[s + B] = np.minimum(dp[s], DX)
            dp[s + 2 * B] = np.minimum(dp[s], DY)
            size[s + B] = size[s + 2 * B] = size[s] + 1
    dp *= P
    cost = dp.sum(axis=1)
    ans = np.full(N + 1, cost[0], np.int64)
    for s in range(3**N):
        n = size[s]
        ans[n] = min(ans[n], cost[s])
    return ans

N = int(readline())
XYP = np.array(read().split(), np.int64)

ans = main(XYP)
print('\n'.join(map(str, ans.tolist())))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n = int(input())

init_score = 0
xy = []
mind = []
Ps = []
for i in range(n):
    x, y, p = map(int, input().split())
    xy.append((x, y))
    Ps.append(p)
    mind.append(min(abs(x), abs(y)))
    init_score += mind[i]*p

print(init_score)

for k in range(1, n+1):
    max_imp = 0
    for subset in combinations(range(2*n), k):
        nmind = mind.copy()
        for v in subset:
            a, b = divmod(v, 2)
            if b == 0:
                x, _ = xy[a]
                for i in range(n):
                    x2, _ = xy[i]
                    new_d = abs(x2-x)
                    if new_d < nmind[i]:
                        nmind[i] = new_d
            else:
                _, y = xy[a]
                for i in range(n):
                    _, y2 = xy[i]
                    new_d = abs(y2-y)
                    if new_d < mind[i]:
                        nmind[i] = new_d

        def calc(ls):
            return sum(abs(x-y)*Ps[i] for i, (x, y) in enumerate(zip(mind, nmind)))
        improve = calc(nmind)
        if max_imp < improve:
            max_imp = improve
    print(init_score-max_imp)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import combinations

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

for rail in range(N+1):
    I=combinations(list(range(N)),rail)

    for rails in I:
        #print(rails)

        for i in range(1<<rail):
            X=[0]
            Y=[0]
            for j in range(rail):
                if (1<<j) & i ==0:
                    X.append(P[rails[j]][0])
                else:
                    Y.append(P[rails[j]][1])

            C=0
            for x,y,p in P:
                MIN=1<<30
                for xx in X:
                    MIN=min(abs(xx-x),MIN)
                for yy in Y:
                    MIN=min(abs(yy-y),MIN)

                C+=MIN*p

            #print(X,Y,C)

            ANS=min(ANS,C)

    print(ANS)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N = int(input())

XYP = []
x = set()
y = set()
for _ in range(N):
    X, Y, P = map(int, input().split())
    if X == 0 or Y == 0:
        continue
    x.add(X)
    y.add(Y)
    XYP.append((X, Y, P))

S = float('inf')
for K in range(N + 1):
    if S != 0:
        S = float('inf')
        for k in range(K + 1):
            for cx in combinations(x, k):
                xx = [0] + list(cx)
                for cy in combinations(y, K - k):
                    yy = [0] + list(cy)
                    t = 0
                    for X, Y, P in XYP:
                        #print("x", xx, "y", yy)
                        m = float('inf')
                        for i in xx:
                            m = min(m, abs(X - i))
                        for i in yy:
                            m = min(m, abs(Y - i))
                        t += m * P
                    S = min(S, t)
        print(S)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
cities = []
S = 0
candx = []
candy = []
for _ in range(N):
    city = [int(i) for i in input().split()]
    candx.append(city[0])
    candy.append(city[1])
    cities.append(city)
    S += city[2]*min(abs(city[0]),abs(city[1]))
print(S)
for i in range(1,N):
    a = 0
    for j in range(i+1):
        for x in itertools.combinations(candx,j):
            for y in itertools.combinations(candy,i-j):
                draft = 0
                x = list(x)
                y = list(y)
                for city in cities:
                    dx = float("inf")
                    dy = float("inf")
                    if x:
                        dx = min([abs(city[0]-k) for k in x])
                    if y:
                        dy = min([abs(city[1]-k) for k in y])
                    draft += city[2]*(min(abs(city[0]),abs(city[1])) - min(abs(city[0]),abs(city[1]),dx,dy))
                a = max(a,draft)
    print(S-a)
print(0)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as BL
N=int(input())
XYP=[list(map(int,input().split())) for _ in range(N)]
ans=[float("inf")]*(N+1)
for i in range(2**N):
  target=[]
  for j in range(N):
    if (i>>j)%2==1:
      target.append(j)
  for j in range(2**len(target)):
    lineX=[-30000,0,30000]
    lineY=[-30000,0,30000]
    for k in range(len(target)):
      if (j>>k)%2==1:
        lineX.insert(BL(lineX,XYP[target[k]][1]),XYP[target[k]][1])
      else:
        lineY.insert(BL(lineY,XYP[target[k]][0]),XYP[target[k]][0])
    temp=0
    for k in range(N):
      if k in target:
        continue
      x,y,p=XYP[k][0],XYP[k][1],XYP[k][2]
      r=lineY[BL(lineY,x)]-x
      l=x-lineY[BL(lineY,x)-1]
      u=lineX[BL(lineX,y)]-y
      d=y-lineX[BL(lineX,y)-1]
      dist=min(r,l,u,d)
      temp+=dist*p
    ans[len(target)]=min(ans[len(target)],temp)
for i in range(N+1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

x = []
y = []
p = []
for i in range(n):
    xx,yy,pp = map(int,input().split())
    x.append(xx+10000)
    y.append(yy+10000)
    p.append(pp)

res = [10**20]*(n+1)


for f in range(2**n):
    kou = []
    for i in range(n):
        if (f>>i)&1 == 1:
            kou.append(i)
    num = len(kou)
    w = set(kou)
    if res[num] == 0:
        continue

    for rr in range(1<<num):
        yoko = set([10000])
        tate = set([10000])

        for i in range(num):
            if (rr>>i)&1 == 1:
                yoko.add(y[kou[i]])
            else:
                tate.add(x[kou[i]])

        tmp = 0
        for i in range(n):
            if i in w:
                continue
            mi = 10**9
            for e in yoko:
                if mi > abs(e-y[i]):
                    mi = abs(e-y[i])
            for e in tate:
                if mi > abs(e-x[i]):
                    mi = abs(e-x[i])
            tmp += p[i]*mi
        
        residx = len(yoko) + len(tate) - 2
        if tmp == 0 and res[residx] != 0:
            for j in range(residx,n+1):
                res[j] = 0
        if residx < n+1 and res[residx] > tmp:
            res[residx] = tmp
for e in res:
    print(e)

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

from itertools import combinations

def resolve():
    n = int(input())
    xyp = [list(map(int, input().split())) for _ in range(n)]

    # 全パターン、先に計算しておく
    # 探索空間
    xx = [x for x, _, _ in xyp]
    yy = [y for _, y, _ in xyp]
    inf = 10 ** 32

    print(sum([min(abs(x), abs(y)) * p for x, y, p in xyp]))

    for i in range(1, n + 1):
        tmp_ans = inf
        for j in range(i + 1):
            for x_list in combinations(xx, j):
                for y_list in combinations(yy, i - j):
                    tmp = sum([
                        min(
                            min([abs(x)] + [abs(x - x_line) for x_line in x_list]),
                            min([abs(y)] + [abs(y - y_line) for y_line in y_list])
                        ) * p for x, y, p in xyp
                    ])

                    if tmp < tmp_ans:
                        tmp_ans = tmp

        print(tmp_ans)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1 2 300
3 3 600
1 4 800"""
        output = """2900
900
0
0"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400"""
        output = """13800
1600
0
0
0
0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200"""
        output = """26700
13900
3200
1200
0
0
0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """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"""
        output = """2576709
1569381
868031
605676
366338
141903
0
0
0"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
N = int(input())
town = [list(map(int,input().split())) for i in range(N)]
X = [town[i][0] for i in range(N)]
Y = [town[i][1] for i in range(N)]
#print(X)
#rint(Y)
for k in range(N+1):
    D = [min(abs(town[i][0]),abs(town[i][1]))*town[i][2] for i in range(N)]
    ans = sum(D)
    for l in range(k+1):
        x = list(itertools.combinations(X,l))
        y = list(itertools.combinations(Y,k-l))
        #print(x)
        #print(y)
        for a in x:
            for b in y:
                d = copy.deepcopy(D)
                for p in a:
                    for i in range(N):
                        d[i] = min(abs(town[i][0]-p)*town[i][2],d[i])
                for q in b:
                    for i in range(N):
                        d[i] = min(abs(town[i][1]-q)*town[i][2],d[i])
                #print(a,b,sum(d))
                ans = min(ans,sum(d))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right, insort_left, insort_right
from functools import reduce

N = a_int()
XYP = read_tuple(N)
X, Y, P = zip(*XYP)
# i=0,1のときは簡単
# i=>2のときにどうするか...
# まてよ、各点について、[なし、縦、横]の三種類の全探索なら3^15=14348907でぎり間に合う
# それで何本鉄道路線を敷いたかのdictに突っ込んであげれば良い
# なかのループも考えると10^9ぐらいになってCppじゃないと間に合わんなぁ

ans = defaultdict(lambda: 10**15 + 1)

for types in product(range(3), repeat=N):
    n_rails = 0
    Xs = [-10**9]  # 縦のrails #単調増加
    Ys = [-10**9]  # 縦のrails #単調増加
    i_walk = []  # 歩くのが必要な集落のidx
    for i, ty in enu(types):
        if ty == 0:  # railsをしかない
            i_walk.append(i)
        elif ty == 1:  # railsを縦に敷く
            Xs.append(X[i])
            n_rails += 1
        else:  # railを横にしく
            Ys.append(Y[i])
            n_rails += 1
    Xs.append(10**9)
    Ys.append(10**9)
    insort_left(Xs, 0)
    insort_left(Ys, 0)
    # 歩くコストの計算
    cost = 0
    for i in i_walk:
        # Xの一番路線
        idx = bisect_left(Xs, X[i])
        d_x = min(abs(Xs[idx] - X[i]), abs(Xs[idx - 1] - X[i]))
        # Yの一番近い路線
        idx = bisect_left(Ys, Y[i])
        # print(idx, Ys, Y)
        d_y = min(abs(Ys[idx] - Y[i]), abs(Ys[idx - 1] - Y[i]))
        cost += min(d_x, d_y) * P[i]

    ans[n_rails] = min(ans[n_rails], cost)

# ans[0] = sum(abs(x) * p for x, p in zip(X, P)) + \
#     sum(abs(y) * p for y, p in zip(Y, P))
for i in range(N + 1):
    print(ans[i])

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)
    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 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 >= n:
            continue
        lx.sort()
        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
N = int(input())
X = []
Y = []
P = []
for i in range(N):
    x, y, p = map(int, input().split())
    X += [x]
    Y += [y]
    P += [p]
base_list = [i for i in range(N)]
base_cost = [min(abs(x), abs(y)) * p for x, y, p in zip(X, Y, P)]
# print(base_cost)
for k in range(0, N+1):
    ans = sum(base_cost)
    # comb_gen = itertools.combinations(base_list, k)
    for b in range(2**k):
        comb_gen = itertools.combinations(base_list, k)
        for comb in comb_gen:
            cost = base_cost.copy()
            for j, ci in enumerate(comb):
                if (b >> j) & 1:
                    for i in range(N):
                        cost[i] = min(abs(Y[ci]-Y[i]) * P[i], cost[i])
                else:
                    for i in range(N):
                        cost[i] = min(abs(X[ci]-X[i]) * P[i], cost[i])
            ans = min(ans, sum(cost))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math, itertools

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


def S(st_xs, st_ys):
    ans = 0
    for x, y, p in XYP:
        d = abs(x)
        for st_x in st_xs:
            d = min(d, abs(x - st_x))
        for st_y in st_ys:
            d = min(d, abs(y - st_y))
        ans += d*p
    return ans


ans = S([0], [0])
streets = [(x, y) for x, y, _ in XYP]
for k in range(N):
    if ans == 0:
        print(0)
        continue
    for sts in itertools.combinations(streets, k):
        for mask in range(2**k):
            st_xs = [0]
            st_ys = [0]
            for i in range(k):
                if mask>>i&1:
                    st_xs.append(sts[i][0])
                else:
                    st_ys.append(sts[i][1])
            ans = min(ans, S(st_xs, st_ys))
    print(ans)
print(0)