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 io
import os

from collections import Counter, defaultdict, deque

inf = float("inf")


def powersetOfMask(mask):
    yield mask
    subset = mask
    while subset:
        subset = (subset - 1) & mask
        yield subset


def solve(N, XYP):
    popcount = []
    for mask in range(1 << N):
        popcount.append(bin(mask).count("1"))

    ans = [inf for i in range(N + 1)]

    for mask in range(1 << N):
        K = popcount[mask]
        if K == 0:
            # No extra
            cost = 0
            for x, y, p in XYP:
                cost += min(abs(x - 0), abs(y - 0)) * p
            ans[K] = min(ans[K], cost)
        else:
            # Building extra railroads, choose which are horiz/vert
            for hMask in powersetOfMask(mask):
                vMask = mask - hMask
                cost = 0
                for i, (x, y, p) in enumerate(XYP):
                    # Dist to axis
                    bestH = abs(x)
                    bestV = abs(y)
                    # Dist to horiz or vert railroads
                    for j in range(N):
                        x2, y2, _ = XYP[j]
                        if hMask & (1 << j):
                            bestH = min(bestH, abs(x - x2))
                        if vMask & (1 << j):
                            bestV = min(bestV, abs(y - y2))
                    cost += min(bestH, bestV) * p
                ans[K] = min(ans[K], cost)

    return "\n".join(str(ans[K]) for K in range(N + 1))


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    (N,) = [int(x) for x in input().split()]
    XYP = [[int(x) for x in input().split()] for i in range(N)]
    ans = solve(N, XYP)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from bisect import bisect_left

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

ans = 0
for x, y, p in xyp:
    ans += min(abs(x), abs(y)) * p
print(ans)

for i in range(1, n + 1):
    ans = 10 ** 20
    for lst in itertools.combinations(range(n), i):
        for xy_lst in itertools.product(range(2), repeat = i):
            tmp = 0
            x_lst = []
            y_lst = []
            for j, xy in zip(lst, xy_lst):
                if xy == 0:
                    x_lst.append(xyp[j][0])
                else:
                    y_lst.append(xyp[j][1])
                x_lst.sort()
                y_lst.sort()
            for x, y, p in xyp:
                x_pos = bisect_left(x_lst, x)
                y_pos = bisect_left(y_lst, y)
                tmp2 = min(abs(x), abs(y))
                try:
                    tmp2 = min(abs(x - x_lst[x_pos]), tmp2)
                except IndexError:
                    pass
                try:
                    tmp2 = min(tmp2, abs(x - x_lst[x_pos - 1]))
                except IndexError:
                    pass
                
                try:
                    tmp2 = min(tmp2, abs(y - y_lst[y_pos]))
                except IndexError:
                    pass
                try:
                    tmp2 = min(tmp2, abs(y - y_lst[y_pos - 1]))
                except IndexError:
                    pass
                tmp += tmp2 * p

            ans = min(ans, tmp)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, product


def get_time_to_nearest_line(x, y, ew_lines, ns_lines):
    ew_min = min(abs(l - y) for l in ew_lines)
    ns_min = min(abs(l - x) for l in ns_lines)
    return min(ew_min, ns_min)


def get_cost(ew_lines, ns_lines):
    return sum(
        p * get_time_to_nearest_line(x, y, ew_lines, ns_lines) for x, y, p in districts
    )


N = int(input())
districts = [list(map(int, input().split())) for _ in range(N)]
init_cost = get_cost([0], [0])
is_cost_zero = False
for K in range(N + 1):
    min_cost = init_cost
    for do_construct_along_ew in product([True, False], repeat=K):
        for stations in combinations(districts, K):
            ew = [0]
            ns = [0]
            for i, (x, y, p) in enumerate(stations):
                if do_construct_along_ew[i]:
                    ew.append(y)
                else:
                    ns.append(x)
            min_cost = min(min_cost, get_cost(ew, ns))
            if min_cost == 0:
                is_cost_zero = True
                break
        if is_cost_zero:
            break
    if is_cost_zero:
        print("\n".join(["0"] * (N - K + 1)))
        exit()
    print(min_cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    tot=0
    base=[0]*N
    for i,(x,y,p) in enumerate(S):
        ta=min(abs(x),abs(y))*p
        base[i]=ta
        tot+=ta

    print(tot)
    inf=tot
    ts=list(range(N))
    for i in range(1,N+1):
        ans=inf
        for t in combinations(ts,i):
            t=list(t)
            for j in range(2**i):
                l=copy(base)
                for k in range(i):
                    if (j>>k)&1:
                        for li in range(N):
                            l[li]=min(l[li],abs(S[li][1]-S[t[k]][1])*S[li][2])
                    else:
                        for li in range(N):
                            l[li]=min(l[li],abs(S[li][0]-S[t[k]][0])*S[li][2])
                ans=min(ans,sum(l))
        print(ans)
                
                
    




if __name__ == "__main__":
    main()

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)

    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 residx < n+1 and res[residx] > tmp:
            res[residx] = tmp
for e in res:
    print(e)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
INF = 10**12

def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)


def main():
    N = int(input())
    X = [None] * N
    Y = [None] * N
    P = [None] * N
    for i in range(N):
        X[i], Y[i], P[i] = map(int, input().split())
    
    ans = [INF] * (N+1)

    # 逆順から考えていく
    # 0:なし、1:南北、2:東西
    for i in range(3**N):
        s = Base_10_to_n(i,3).zfill(N)
        # コストが0にならない町
        not0 = []
        for j in range(N):
            if s[j] == '0':
                not0.append(j)
        
        # コストを計算する
        tmp = 0
        for n in not0:
            # 距離の最短を計算する
            tmp2 = min(abs(X[n]),abs(Y[n]))
            for j in range(N):
                if s[j] == '1':
                    tmp2 = min(tmp2, abs(X[j]-X[n]))
                elif s[j] == '2':
                    tmp2 = min(tmp2, abs(Y[j]-Y[n]))
            tmp += P[n] * tmp2
            # print(tmp2)
        # print(s,not0,tmp)
        ans[len(not0)] = min(ans[len(not0)], tmp)
    [print(a) for a in ans[::-1]]

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)


def main():
    N = int(input())
    X = [None] * N
    Y = [None] * N
    P = [None] * N
    for i in range(N):
        X[i], Y[i], P[i] = map(int, input().split())
    
    ans = [INF] * (N+1)

    # 逆順から考えていく
    # 0:なし、1:南北、2:東西
    for i in range(3**N):
        s = Base_10_to_n(i,3).zfill(N)
        # コストが0にならない町
        not0 = []
        for j in range(N):
            if s[j] == '0':
                not0.append(j)
        
        # コストを計算する
        tmp = 0
        for n in not0:
            # 距離の最短を計算する
            tmp2 = min(abs(X[n]),abs(Y[n]))
            for j in range(N):
                if s[j] == '1':
                    tmp2 = min(tmp2, abs(X[j]-X[n]))
                elif s[j] == '2':
                    tmp2 = min(tmp2, abs(Y[j]-Y[n]))
            tmp += P[n] * tmp2
            # print(tmp2)
        # print(s,not0,tmp)
        ans[len(not0)] = min(ans[len(not0)], tmp)
    [print(a) for a in ans[::-1]]


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
cities = []
for i in range(N):
    X,Y,P = map(int,input().split())
    cities.append([X,Y,P])
line = [float('inf')]*(N+1)
costs = []
for x,y,p in cities:
    costs.append(p*min(abs(x),abs(y)))

def func(D,V,K):
    if D == N:
        return
    queue = []
    if V == 0:
        K -= 1
    if V == 1:
        X = cities[D][0]
        for i in range(N):
            ncost = abs(cities[i][0]-X)*cities[i][2]
            if costs[i] > ncost:
                queue.append((i,costs[i]))
                costs[i] = ncost
    if V == 2:
        Y = cities[D][1]
        for i in range(N):
            ncost = abs(cities[i][1]-Y)*cities[i][2]
            if costs[i] > ncost:
                queue.append((i,costs[i]))
                costs[i] = ncost
    line[K] = min(line[K],sum(costs))
    for i in range(3):
        func(D+1,i,K)
    for i,cost in queue:
        costs[i] = cost

for i in range(3):
    func(0,i,N)

for i in line:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import bisect

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as cmb

N=int(input())
X=[]
Y=[]
data=[]
ans=0
for _ in range(N):
    x,y,p=map(int,input().split())
    data.append([x,y,p])
    ans+=min(abs(x),abs(y))*p
    if x not in X:
        X.append(x)
    if y not in Y:
        Y.append(y+10**6)
print(ans)
for i in range(1,N):
    if ans==0:
        print(0)
        continue

    cand=list(cmb(X+Y,i))
    for c in cand:
        temp=0
        for j in range(N):
            d=min(abs(data[j][0]),abs(data[j][1]))
            for w in c:
                if w<=10**5:
                    d=min(d,abs(data[j][0]-int(w)))
                else:
                    d=min(d,abs(data[j][1]-int(w)+10**6))
            temp+=d*data[j][2]
        ans=min(ans,temp)
    print(ans)
print(0)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, product


def get_time_to_nearest_line(x, y, ew_lines, ns_lines):
    ew_min = min(abs(l - y) for l in ew_lines)
    ns_min = min(abs(l - x) for l in ns_lines)
    return min(ew_min, ns_min)


def get_cost(ew_lines, ns_lines):
    return sum(
        p * get_time_to_nearest_line(x, y, ew_lines, ns_lines) for x, y, p in districts
    )


N = int(input())
districts = [list(map(int, input().split())) for _ in range(N)]
init_cost = get_cost([0], [0])
for K in range(N + 1):
    min_cost = init_cost
    for do_construct_along_ew in product([True, False], repeat=K):
        for stations in combinations(districts, K):
            ew = [0]
            ns = [0]
            for i, (x, y, p) in enumerate(stations):
                if do_construct_along_ew[i]:
                    ew.append(y)
                else:
                    ns.append(x)
            min_cost = min(min_cost, get_cost(ew, ns))
    print(min_cost)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import combinations
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y,P=[0]*N,[0]*N,[0]*N
for i in range(N):
    X[i],Y[i],P[i]=map(int,input().split())
for k in range(N+1):
    ans=INF
    for p in combinations(range(N),k):
        for i in range(2**k):
            tate=[0]*k
            for j in range(k):
                tate[j]=(i>>j)&1
            S=[min(abs(Y[i]),abs(X[i]))*P[i] for i in range(N)]
            for j in range(k):
                for i in range(N):
                    if tate[j]:
                        S[i]=min(S[i],abs(Y[i]-Y[p[j]])*P[i])
                    else:
                        S[i]=min(S[i],abs(X[i]-X[p[j]])*P[i])
            ans=min(ans,sum(S))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
#print(a)
tableud = [[0] * N for _ in range(N)]
tablelr = [[0] * N for _ in range(N)]
for i in range(N):
  x, y, _ = a[i]
  for j in range(N):
    tableud[i][j] = abs(a[j][0] - x) * a[j][2]
    tablelr[i][j] = abs(a[j][1] - y) * a[j][2]
for t in range(N + 1):
  res = float("inf")
  for c in combi([x for x in range(N)], t):
    for i in range(1 << t):
      table = [10 ** 20] * N
      for j in range(N):
        table[j] = min(abs(a[j][0]), abs(a[j][1])) * a[j][2]
      for j in range(t):
        if i & (1 << j):
          for k in range(N):
            table[k] = min(table[k], tableud[c[j]][k])
        else:
          for k in range(N):
            table[k] = min(table[k], tablelr[c[j]][k])
      res = min(res, sum(table))
  print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations

def solve():
      input = sys.stdin.readline
      N = int(input())
      Ans = [10 ** 10] * (N + 1)
      Ans[0] = 0
      Res = [None] * N
      for i in range(N):
            Res[i] = [int(j) for j in input().split()]
            Ans[0] += min(abs(Res[i][0]), abs(Res[i][1])) * Res[i][2] 
      D = [min(abs(Res[i][0]), abs(Res[i][1])) for i in range(N)]
      
      for p in permutations(range(N)):
            Dist = [D[i] for i in range(N)]
            Move = Ans[0]
            for j in range(N):
                  k = p[j]
                  Move -= Dist[k] * Res[k][2]
                  Dist[k] = 0
                  EW, NS = 0, 0
                  for r in range(N):
                        EW += max(0, Dist[r] - abs(Res[r][1] - Res[k][1])) * Res[r][2]
                        NS += max(0, Dist[r] - abs(Res[r][0] - Res[k][0])) * Res[r][2]
                  if EW >= NS:
                        Move -= EW
                        for r in range(N):
                             Dist[r] = min(Dist[r], abs(Res[r][1] - Res[k][1]))
                  else:
                        Move -= NS
                        for r in range(N):
                              Dist[r] = min(Dist[r], abs(Res[r][0] - Res[k][0]))
                  Ans[j+1] = min(Move, Ans[j+1])
      print(*Ans, sep="\n")

      return 0

if __name__ == "__main__":
      solve()

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    ans = [float("inf")] * (N+1)
    for i in range(3**N):
        M = i
        L = []
        k = 0
        Xline = [0]
        Yline = [0]
        for j in range(N):
            if M%3 == 0:
                L.append(XYP[j])
            elif M%3 == 1:
                k += 1
                Xline.append(XYP[j][0])
            else:
                k += 1
                Yline.append(XYP[j][1])
            M //= 3
        cost = 0
        for x, y, p in L:
            d = 10**6
            for xx in Xline:
                d = min(d, abs(x - xx))
            for yy in Yline:
                d = min(d, abs(y - yy))
            cost += d * p
        ans[k] = min(ans[k], cost)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
XYP = [tuple(map(int,input().split())) for i in range(N)]

from itertools import combinations
xset = set()
yset = set()
ycands = []
for x,y,_ in XYP:
    if x!=0: xset.add(x)
    if y!=0: yset.add(y)

xl = list(xset)
yl = list(yset)

def cost(xs,ys):
    ret = 0
    for x,y,p in XYP:
        tmp = 10**9
        for xx in xs:
            tmp = min(tmp, abs(xx-x))
        for yy in ys:
            tmp = min(tmp, abs(yy-y))
        ret += tmp * p
    return ret

for k in range(N+1):
    if k >= len(xl) or k >= len(yl):
        print(0)
        continue
    ans = 10**20
    for xc in range(k+1):
        yc = k-xc
        for xs in combinations(xl,xc):
            xs = list(xs) + [0]
            for ys in combinations(yl,yc):
                ys = list(ys) + [0]
                ans = min(ans, cost(xs,ys))
    print(ans)

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)

    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):
            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 residx < n+1 and res[residx] > tmp:
            res[residx] = tmp
for e in res:
    print(e)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

for k in range(n+1):
    if k == n:
        print(0)
    else:
        ans = 10**20
        ptr = list(itertools.combinations(seq,k))
        ptr2 = list(itertools.product((0,1), repeat=k))
        for i in ptr:
            for j in ptr2:
                x = [0]
                y = [0]
                tmp = 0
                for cnt in range(k):
                    if j[cnt] == 0:
                        x.append(xyp[i[cnt]][0])
                    else:
                        y.append(xyp[i[cnt]][1])
                for ii in range(n):
                    min1 = 10**10
                    xx,yy,p = xyp[ii]
                    for x1 in x:
                        min1 = min(min1, abs(x1-xx))
                    for y1 in y:
                        min1 = min(min1, abs(y1-yy))
                    tmp += min1 * p
                ans = min(ans, tmp)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
import itertools
n = int(input())
town = []
for i in range(n):
    x,y,p = map(int,input().split())
    town.append((x,y,p))

ans = [10**20]*(n+1)
for flags in itertools.product((0,1,2),repeat = n):
    roadx = [-10**5,0,10**5]
    roady = [-10**5,0,10**5]
    cnt = 0
    for i,(flag,(x,y,p)) in enumerate(zip(flags,town)):
        if flag == 1:
            roadx.append(x)
            cnt += 1
        elif flag == 2:
            roady.append(y)
            cnt += 1
    roadx.sort()
    roady.sort()
    s = 0
    for x,y,p in town:
        bx = bisect_right(roadx, x)
        by = bisect_right(roady, y)
        m = min(x - roadx[bx-1], roadx[bx] - x, y - roady[by-1], roady[by] - y)
        s += m*p
    ans[cnt] = min(ans[cnt], s)
print("\n".join(str(i) for i in ans))

Submission status: Memory Limit Exceeded

Solution code:
import sys
import numpy as np

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

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)) * P
    size = np.empty(3**N, np.int64)
    size[0] = 0
    for n in range(N):
        B = 3**n
        DX = np.abs(X - X[n]) * P
        DY = np.abs(Y - Y[n]) * P
        dp[B:2 * B] = np.minimum(dp[:B], DX)
        dp[2 * B:3 * B] = np.minimum(dp[:B], DY)
        size[B:2 * B] = size[:B] + 1
        size[2 * B:3 * B] = size[:B] + 1
    ans = np.full(N + 1, 10**18, np.int64)
    for s in range(3**N):
        n = size[s]
        ans[n] = min(ans[n], dp[s].sum())
    return ans

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i8[:], ))
    cc.compile()

from my_module import main

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

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

Submission status: Accepted

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

def caldp(a):
    n = len(a)
    a.sort()
    dp = [[float("INF")]*(n+1) for i in range(n+1)]
    dp[0][0] = 0
    for l in range(n):
        for r in range(l+1,n+1):
            now = float("INF")
            for k in range(l,r):
                count = 0
                for i in range(l,r):
                    count += abs(a[i][0]-a[k][0])*a[i][1]
                    if count >= now:
                        break
                now = min(now,count)
            for j in range(n):
                dp[r][j+1] = min(dp[r][j+1],dp[l][j]+now)

            now = 0
            for i in range(l,r):
                now += abs(a[i][0])*a[i][1]
            for j in range(n+1):
                dp[r][j] = min(dp[r][j],dp[l][j]+now)

    res = [float("INF")]*(n+1)
    for i in range(n+1):
        res[i] = dp[-1][i]
    return res

ans = [float("INF")]*(n+1)

for s in range(1<<n):
    lx = []
    ly = []
    for i in range(n):
        if s >> i & 1:
            lx.append((xyp[i][0],xyp[i][2]))
        else:
            ly.append((xyp[i][1],xyp[i][2]))
    lx = caldp(lx)
    ly = caldp(ly)
    for i in range(len(lx)):
        for j in range(len(ly)):
            ans[i+j] = min(ans[i+j],lx[i]+ly[j])

for i in ans:
    print(i)