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:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    N = int(input())
    X = [0]*N
    Y = [0]*N
    P = [0]*N
    for i in range(N):
        X[i], Y[i], P[i] = map(int, input().split())
    
    # costs using only vertical roads
    cost_v = [[min(abs(X[n]), abs(Y[n]))*P[n] for n in range(N)] for _ in range(2**N)]
    for i in range(2**N):
        for bit in range(N):
            if i & (1 << bit):
                for n in range(N):
                    cost_v[i][n] = min(cost_v[i][n], abs(X[bit] - X[n])*P[n])

    # costs using only horizontal roads
    cost_h = [[min(abs(X[n]), abs(Y[n]))*P[n] for n in range(N)] for _ in range(2**N)]
    for i in range(2**N):
        for bit in range(N):
            if i & (1 << bit):
                for n in range(N):
                    cost_h[i][n] = min(cost_h[i][n], abs(Y[bit] - Y[n])*P[n])

    # calculate for all cases
    ans = [INF]*(N+1)
    for i in range(3**N):
        digits = [0] * N
        for d in range(N):
            digits[d] = i % 3
            i = i // 3
        
        cnt = 0             # number of roads
        v = 0
        h = 0
        for d in range(N):
            if digits[d] == 1:
                cnt += 1
                v += 1 << d
            elif digits[d] == 2:
                cnt += 1
                h += 1 << d
        
        tmp = 0
        for n in range(N):
            tmp += min(cost_v[v][n], cost_h[h][n])
        ans[cnt] = min(tmp, ans[cnt])
    
    for k in range(N+1):
        print(ans[k])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    N = int(input())
    X = [0]*N
    Y = [0]*N
    P = [0]*N
    for i in range(N):
        X[i], Y[i], P[i] = map(int, input().split())
    
    # costs using only vertical roads
    cost_v = [[min(abs(X[n]), abs(Y[n]))*P[n] for n in range(N)] for _ in range(2**N)]
    for i in range(2**N):
        for bit in range(N):
            if i & (1 << bit):
                for n in range(N):
                    cost_v[i][n] = min(cost_v[i][n], abs(X[bit] - X[n])*P[n])

    # costs using only horizontal roads
    cost_h = [[min(abs(X[n]), abs(Y[n]))*P[n] for n in range(N)] for _ in range(2**N)]
    for i in range(2**N):
        for bit in range(N):
            if i & (1 << bit):
                for n in range(N):
                    cost_h[i][n] = min(cost_h[i][n], abs(Y[bit] - Y[n])*P[n])

    # calculate for all cases
    ans = [INF]*(N+1)
    for i in range(3**N):
        digits = [0] * N
        for d in range(N):
            digits[d] = i % 3
            i = i // 3
        
        cnt = 0             # number of roads
        v = 0
        h = 0
        for d in range(N):
            if digits[d] == 1:
                cnt += 1
                v += 2**d
            elif digits[d] == 2:
                cnt += 1
                h += 2**d
        
        tmp = 0
        for n in range(N):
            tmp += min(cost_v[v][n], cost_h[h][n])
        ans[cnt] = min(tmp, ans[cnt])
    
    for k in range(N+1):
        print(ans[k])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3

import sys
import numpy as np
from itertools import combinations
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

x_cost = [[0 for _ in range(N)] for _ in range(1 << N)]
y_cost = [[0 for _ in range(N)] for _ in range(1 << N)]

for bit in range(1 << N):
    for i in range(N):
        x_cost[bit][i] = abs(XYP[i][0])
        y_cost[bit][i] = abs(XYP[i][1])

        for k in range(N):
            if bit & (1 << k):
                x_cost[bit][i] = min(x_cost[bit][i], abs(XYP[i][0] - XYP[k][0]))
                y_cost[bit][i] = min(y_cost[bit][i], abs(XYP[i][1] - XYP[k][1]))

ans = [sys.maxsize for _ in range(N + 1)]

for bit in range(1 << N):
    cnt = bin(bit).count('1')
    for i in range(bit, -1, -1):
        i &= bit
        cost = 0
        for k in range(N):
            if ~(bit & (1 << k)):
                cost += 1 * XYP[k][2] * min(x_cost[i][k], y_cost[bit - i][k])
        ans[cnt] = min(ans[cnt], cost)

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()



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

idle_max=10**18

def main():
    sumc=0
    for x,y,p in XYP:
        c=idle_max
        for X in Xlst:
            c=min(round(abs(X-x))*p,c)
        for Y in Ylst:
            c=min(round(abs(Y-y))*p,c)
        sumc+=c
    return (sumc)

scorelst=[idle_max for i in range(N)]
for bit in product(range(2), repeat=N):
    Xlst=[0]
    Ylst=[0]
    for l in range(N):
        score=idle_max
        if bit[l]:
            reX=idle_max
            for n in range(N):
                x,y,p=XYP[n]
                Xlst.append(x)
                _score=main()
                if _score<score:
                    reX=x
                    score=_score
                    scorelst[l]=min(scorelst[l],_score)
                Xlst.pop()
            Xlst.append(reX)
        else:
            reY=idle_max
            for n in range(N):
                x,y,p=XYP[n]
                Ylst.append(y)
                _score=main()
                if _score<score:
                    reY=y
                    score=_score
                    scorelst[l]=min(scorelst[l],_score)
                Ylst.pop()
            Ylst.append(reY)
    #print(bit,Xlst,Ylst)
Xlst=[0]
Ylst=[0]
print(main())
for score in scorelst:
    print(score)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    n = I()
    p = LIR(n)
    p.sort()
    m = 1<<n
    s = 0
    for i,(x,y,num) in enumerate(p):
        d = min(abs(x),abs(y))
        s += num*d
    ans = [s]*(n+1)
    ans[-1] = 0
    pow = [1<<i for i in range(n)]
    dx = [[None]*m for i in range(n)]
    dy = [[None]*m for i in range(n)]
    for b in range(m):
        lx = []
        ly = []
        res = b
        for x,y,_ in p:
            j = res&1
            if j:
                lx.append(x)
                ly.append(y)
            res >>= 1
        ly.sort()
        for j,(x,y,num) in enumerate(p):
            i = bisect.bisect_left(lx,x)-1
            dxj = abs(x)
            dyj = abs(y)
            if i >= 0:
                nd = x-lx[i]
                if nd < dxj:
                    dxj = nd
            i += 1
            if i < len(lx):
                nd = lx[i]-x
                if nd < dxj:
                    dxj = nd
            i += 1
            if i < len(lx):
                nd = lx[i]-x
                if nd < dxj:
                    dxj = nd
            i = bisect.bisect_left(ly,y)-1
            if i >= 0:
                nd = y-ly[i]
                if nd < dyj:
                    dyj = nd
            i += 1
            if i < len(ly):
                nd = ly[i]-y
                if nd < dyj:
                    dyj = nd
            i += 1
            if i < len(ly):
                nd = ly[i]-y
                if nd < dyj:
                    dyj = nd
            dx[j][b] = dxj*num
            dy[j][b] = dyj*num
    m = 3**n
    for b in range(m):
        kx = ky = cnt = 0
        res = b
        for i in range(n):
            j = res%3
            if j:
                cnt += 1
                if j == 1:
                    kx |= pow[i]
                else:
                    ky |= pow[i]
            res //= 3
        s = 0
        ans_ = ans[cnt]
        for i in range(n):
            d = min(dx[i][kx],dy[i][ky])
            s += d
            if s >= ans_:
                break
        else:
            ans[cnt] = s
    for i in ans:
        print(i)
    return

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

Submission status: Time Limit Exceeded

Solution code:
def score(CITIES, lines, lower_bound, city_lines, city_scores):
    s = 0
    for cityid in range(len(CITIES)):
        x = CITIES[cityid][0]
        y = CITIES[cityid][1]
        p = CITIES[cityid][2]

        for ctl in city_lines[cityid]:
            if ctl in lines:
                s += city_scores[cityid][ctl]
                break
        if s >= lower_bound:
            return lower_bound
    return s

def recursive_score(K, CITIES, candidate_lines, selected, min_select, lower_bound, city_lines, city_scores):
    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, lower_bound, city_lines, city_scores)

    min_score = lower_bound
    i = min_select
    while i < len(candidate_lines):
        if i % 2 == 0:
            next_min_select = i + 2 # 同じ都市に縦線と横線を両方置くのは無駄
        else:
            next_min_select = i + 1
        sel = selected + [i]
        s = recursive_score(K, CITIES, candidate_lines, sel, next_min_select, min_score, city_lines, city_scores)
        if s == 0:
            return 0
        min_score = min(min_score, s)
        i += 1

    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座標が同じで縦線
    candidate_lines = candidate_lines_org

    # 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

    # 線-都市ペアでのscoreを事前計算
    score_target_lines = candidate_lines + [(0, "H"), (0, "V")]
    city_lines = {}
    city_scores = {}
    for i in range(N):
        cityid_score = []

        x = CITIES[i][0]
        y = CITIES[i][1]
        p = CITIES[i][2]
        for l in score_target_lines:
            if l[1] == "H":
                dist = abs(y-l[0])
            else:
                dist = abs(x-l[0])
            cityid_score.append((dist*p, l))

        city_lines[i] = []
        for score, line in sorted(cityid_score, key=lambda x:x[0]):
            city_lines[i].append(line)
            if i not in city_scores:
                city_scores[i] = {}
            city_scores[i][line] = score

    lower_bound = 1000000000000
    for K in range(N+1):
        if lower_bound == 0:
            S = 0
        else:
            S = recursive_score(K, CITIES, candidate_lines, [], 0, lower_bound, city_lines, city_scores)
        print(S)
        lower_bound = S


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
xyp = [None]*n
for i in range(n):
    x,y,p = tuple(map(int, input().split()))
    xyp[i] = (x,y,p,i)
xyp0 = sorted(xyp, key=lambda x: x[0])
xyp1 = sorted(xyp, key=lambda x: x[1])

ans = [float("inf")]*(n+1)
dx = [[None]*(1<<n) for _ in range(n)]
dy = [[None]*(1<<n) for _ in range(n)]
for b in range(1<<n):
    xs = [0]
    ys = [0]
    for i in range(n):
        if b>>i&1:
            xs.append(xyp[i][0])
            ys.append(xyp[i][1])
    for i in range(n):
        dx[i][b] = xyp[i][2] * min(abs(xyp[i][0]-x) for x in xs)
        dy[i][b] = xyp[i][2] * min(abs(xyp[i][1]-y) for y in ys)
        
from itertools import product
for b in product(*[range(3) for _ in range(n)]):
    xs = 0
    ys = 0
    num = 0
    for i in range(n):
        if b[i]==1:
            xs |= 1<<i
            num += 1
        elif b[i]==2:
            ys |= 1<<i
            num += 1
    cc = sum(min(dx[i][xs], dy[i][ys]) for i in range(n))
    ans[num] = min(ans[num], cc)
write("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
xyp = [None]*n
for i in range(n):
    x,y,p = tuple(map(int, input().split()))
    xyp[i] = (x,y,p,i)
xyp0 = sorted(xyp, key=lambda x: x[0])
xyp1 = sorted(xyp, key=lambda x: x[1])

ans = [float("inf")]*(n+1)
dx = [[None]*(1<<n) for _ in range(n)]
dy = [[None]*(1<<n) for _ in range(n)]
for b in range(1<<n):
    xs = [0]
    ys = [0]
    for i in range(n):
        if b>>i&1:
            xs.append(xyp[i][0])
            ys.append(xyp[i][1])
    for i in range(n):
        dx[i][b] = min(abs(xyp[i][0]-x) for x in xs)
        dy[i][b] = min(abs(xyp[i][1]-y) for y in ys)
        
from itertools import product
for b in product(*[range(3) for _ in range(n)]):
    xs = 0
    ys = 0
    num = 0
    for i in range(n):
        if b[i]==1:
            xs |= 1<<i
            num += 1
        elif b[i]==2:
            ys |= 1<<i
            num += 1
    cc = sum(xyp[i][2] * min(dx[i][xs], dy[i][ys]) for i in range(n))
    ans[num] = min(ans[num], cc)
write("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    n = I()
    p = LIR(n)
    p.sort()
    m = 1<<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
    pow = [1<<i for i in range(n)]
    dx = [[None]*m for i in range(n)]
    dy = [[None]*m for i in range(n)]
    for b in range(m):
        lx = []
        ly = []
        res = b
        for x,y,_,_ in p:
            j = res&1
            if j:
                lx.append(x)
                ly.append(y)
            res >>= 1
        ly.sort()
        for j,(x,y,num,d) in enumerate(p):
            i = bisect.bisect_left(lx,x)-1
            dxj = d
            dyj = d
            if i >= 0:
                nd = x-lx[i]
                if nd < dxj:
                    dxj = nd
            i += 1
            if i < len(lx):
                nd = lx[i]-x
                if nd < dxj:
                    dxj = nd
            i = bisect.bisect_left(ly,y)-1
            if i >= 0:
                nd = y-ly[i]
                if nd < dyj:
                    dyj = nd
            i += 1
            if i < len(ly):
                nd = ly[i]-y
                if nd < dyj:
                    dyj = nd
            dx[j][b] = dxj*num
            dy[j][b] = dyj*num
    m = 3**n
    for b in range(m):
        kx = ky = cnt = 0
        res = b
        for i in range(n):
            j = res%3
            if j:
                cnt += 1
                if j == 1:
                    kx |= pow[i]
                else:
                    ky |= pow[i]
            res //= 3
        s = 0
        if ans[cnt] <= 0:
            continue
        ans_ = ans[cnt]
        for i in range(n):
            d = min(dx[i][kx],dy[i][ky])
            s += d
            if s >= ans_:
                break
        else:
            ans[cnt] = s
    for i in ans:
        print(i)
    return

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

Submission status: Time Limit Exceeded

Solution code:
#E
import math
import itertools
import bisect

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 cost_of_K(X,
              Y,
              P,
              x_line=[0],
              y_line=[0]):
    
    total_cost = 0
    x_line = sorted(x_line)
    y_line = sorted(y_line)
    x_len = len(x_line)
    y_len = len(y_line)
    
    for x,y,p in zip(X, Y, P):
        b = bisect.bisect_left(x_line, x)
        b1 = max(0, b-1)
        b2 = min(b, x_len-1)
        x1 = math.fabs(x_line[b1]-x)
        x2 = math.fabs(x_line[b2]-x)
        xmin = min(x1, x2)
        #print(xmin)
        
        b = bisect.bisect_left(y_line, y)
        b1 = max(0, b-1)
        b2 = min(b, y_len-1)
        y1 = math.fabs(y_line[b1]-y)
        y2 = math.fabs(y_line[b2]-y)
        ymin = min(y1, y2)
        #print(ymin)
        
        cost_min = min(xmin, ymin)
        total_cost += p*cost_min
    
    return int(total_cost)

res = cost_of_K(X,
               Y,
               P,
               x_line=[0],
               y_line=[0])
print(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)
    
    icost = 0
    rcost = 0
    
    for c2 in combo:
        xc = [0]
        yc = [0]
        for c in c2:
            if c[0]=="x":
                xc += [int(c[1:])]
            else:
                yc += [int(c[1:])]

            res = cost_of_K(X,
                           Y,
                           P,
                           x_line=xc,
                           y_line=yc)
        
        icost_tmp = 10000./(1+res)
        if icost < icost_tmp:
            icost = icost_tmp
            cost  = res

    print(cost)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def convert(x, n=2, k=0):
    A = []
    while x:
        x, r = divmod(x, n)
        A.append(r)
    return ''.join(map(str, reversed(A))).zfill(k)

n, *XYP = map(int, open(0).read().split())
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))
A = defaultdict(lambda: float('inf'))
A[n] = 0
for i in range(3**n):
    L = [0, 0]
    S = convert(i, 3, n)
    c = S.count('1') + S.count('2')
    for j, (x, y, p) in enumerate(XYP):
        if S[j] == '1':
            L += [x, 0]
        elif S[j] == '2':
            L += [0, y]
    s = 0
    for x, y, p in XYP:
        d_x = min(abs(x-xl) for xl in L[::2])
        d_y = min(abs(y-yl) for yl in L[1::2])
        s += min(d_x, d_y) * p
    if A[c] > s:
        A[c] = s
for i in range(n+1):
    print(A[i])

Submission status: Time Limit Exceeded

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

DX = [[0] * N for _ in range(1 << N)]
DY = [[0] * N for _ in range(1 << N)]

for i, x in enumerate(X):
    for k in range(1 << N):
        d = abs(x)
        for j, xx in enumerate(X):
            if k & (1 << j):
                d = min(d, abs(xx - x))
        DX[k][i] = d * P[i]
for i, y in enumerate(Y):
    for k in range(1 << N):
        d = abs(y)
        for j, yy in enumerate(Y):
            if k & (1 << j):
                d = min(d, abs(yy - y))
        DY[k][i] = d * P[i]

ANS = [1 << 100] * (N + 1)
PC = [0] * (1 << N)
for i in range(1, 1 << N):
    PC[i] = PC[i^1] + 1 if i % 2 else PC[i//2]

mm = (1 << N) - 1
for i in range(1 << N):
    m = i ^ mm
    j = m
    dxi = DX[i]
    while 1:
        dyj = DY[j]
        ans = 0
        for dxik, dyjk in zip(dxi, dyj):
            ans += min(dxik, dyjk)
        
        pc = PC[i] + PC[j]
        ANS[pc] = min(ANS[pc], ans)
        
        if not j:
            break
        j = m & (j - 1)


print(*ANS, sep = "\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
xyp = [None]*n
for i in range(n):
    x,y,p = tuple(map(int, input().split()))
    xyp[i] = (x,y,p,i)
xyp0 = sorted(xyp, key=lambda x: x[0])
xyp1 = sorted(xyp, key=lambda x: x[1])

ans = [float("inf")]*(n+1)
dx = [[None]*(1<<n) for _ in range(n)]
dy = [[None]*(1<<n) for _ in range(n)]
for b in range(1<<n):
    xs = [0]
    ys = [0]
    for i in range(n):
        if b>>i&1:
            xs.append(xyp[i][0])
            ys.append(xyp[i][1])
    for i in range(n):
        dx[i][b] = min(abs(xyp[i][0]-x) for x in xs)
        dy[i][b] = min(abs(xyp[i][1]-y) for y in ys)
        
def ccost(xs, ys):
    val = 0
    return sum(xyp[i][2] * min(dx[i][xs], dy[i][ys]) for i in range(n))
from itertools import product
# for b in product(*[range(3) for _ in range(n)]):
for b in range(pow(3,n)):
    xs = 0
    ys = 0
    num = 0
    for i in range(n):
        if b%3==1:
            xs |= 1<<i
            num += 1
        elif b%3==2:
            ys |= 1<<i
            num += 1
        b //= 3
    cc = ccost(xs, ys)
#     print(b,xs,ys,cc,num)
    ans[num] = min(ans[num], cc)
write("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

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

idle_max=10**18

def main(Xlst,Ylst):
    sumc=0
    for x,y,p in XYP:
        c=idle_max
        for X in Xlst:
            c=min(round(abs(X-x))*p,c)
        for Y in Ylst:
            c=min(round(abs(Y-y))*p,c)
        sumc+=c
    return (sumc)

scorelst=[idle_max for i in range(N)]
for bit in list(product(range(2), repeat=N)):
    Xlst=[0]
    Ylst=[0]
    for l in range(N):
        score=idle_max
        if bit[l]:
            reX=idle_max
            for n in range(N):
                x,y,p=XYP[n]
                tempXlst=copy.copy(Xlst)
                tempXlst.append(x)
                _score=main(tempXlst,Ylst)
                if _score<score:
                    reX=x
                    score=_score
                    scorelst[l]=min(scorelst[l],_score)
            Xlst.append(reX)
        else:
            reY=idle_max
            for n in range(N):
                x,y,p=XYP[n]
                tempYlst=copy.copy(Ylst)
                tempYlst.append(y)
                _score=main(Xlst,tempYlst)
                if _score<score:
                    reY=y
                    score=_score
                    scorelst[l]=min(scorelst[l],_score)
            Ylst.append(reY)
    #print(bit,Xlst,Ylst)
print(main([0],[0]))
for score in scorelst:
    print(score)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
xyp = [None]*n
cost = [None]*n
for i in range(n):
    x,y,p = tuple(map(int, input().split()))
    xyp[i] = (x,y,p,i)
    cost[i] = min(abs(xyp[i][0]), abs(xyp[i][1]))
xyp0 = sorted(xyp, key=lambda x: x[0])
xyp1 = sorted(xyp, key=lambda x: x[1])

def ccost(cost):
    return sum(cost[i]*xyp[i][2] for i in range(n))
ans = [float("inf")]*(n+1)
dx = [[None]*(1<<n) for _ in range(n)]
dy = [[None]*(1<<n) for _ in range(n)]
for b in range(1<<n):
    xs = [0]
    ys = [0]
    for i in range(n):
        if b>>i&1:
            xs.append(xyp[i][0])
            ys.append(xyp[i][1])
    for i in range(n):
        dx[i][b] = min(abs(xyp[i][0]-x) for x in xs)
        dy[i][b] = min(abs(xyp[i][1]-y) for y in ys)
        
def ccost(xs, ys):
    val = 0
    return sum(xyp[i][2] * min(dx[i][xs], dy[i][ys]) for i in range(n))
#     xmins = [float("inf")] * n
#     ymins = [float("inf")] * n
#     xs.sort()
#     ys.sort()
#     j = 0
#     for i in range(n):
#         x,y,p,ind = xyp0[i]
#         xm = abs(x-xs[j])
#         while j+1<len(xs) and xm>abs(x-xs[j+1]):
#             j += 1
#             xm = abs(x-xs[j])
#         xmins[ind] = xm
#     j = 0
#     for i in range(n):
#         x,y,p,ind = xyp1[i]
#         ym = abs(y-ys[j])
#         while j+1<len(ys) and ym>abs(y-ys[j+1]):
#             j += 1
#             ym = abs(y-ys[j])
#         ymins[ind] = ym
#     return sum(item[2]*min(xx,yy) for item,xx,yy in zip(xyp, xmins, ymins))
from itertools import product
for b in product(*[range(3) for _ in range(n)]):
    xs = 0
    ys = 0
    num = 0
    for i in range(n):
        if b[i]==1:
            xs |= 1<<i
            num += 1
        elif b[i]==2:
            ys |= 1<<i
            num += 1
    cc = ccost(xs, ys)
#     print(b,xs,ys,cc,num)
    ans[num] = min(ans[num], cc)
write("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

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

DX = [[0] * (1 << N) for _ in range(N)]
DY = [[0] * (1 << N) for _ in range(N)]

for i, x in enumerate(X):
    for k in range(1 << N):
        d = abs(x)
        for j, xx in enumerate(X):
            if k & (1 << j):
                d = min(d, abs(xx - x))
        DX[i][k] = d * P[i]
for i, y in enumerate(Y):
    for k in range(1 << N):
        d = abs(y)
        for j, yy in enumerate(Y):
            if k & (1 << j):
                d = min(d, abs(yy - y))
        DY[i][k] = d * P[i]

ANS = [1 << 100] * (N + 1)
PC = [0] * (1 << N)
for i in range(1, 1 << N):
    PC[i] = PC[i^1] + 1 if i % 2 else PC[i//2]

RA = []
for i in range(1 << N):
    t = []
    for j in range(N):
        if i & (1 << j):
            t.append(j)
    RA.append(t)

mm = (1 << N) - 1
for i in range(1 << N):
    m = i ^ mm
    j = m
    while 1:
        ans = 0
        for k in RA[i^j^mm]:
            ans += min(DX[k][i], DY[k][j])
        
        pc = PC[i] + PC[j]
        ANS[pc] = min(ANS[pc], ans)
        
        if not j:
            break
        j = m & (j - 1)
for i in range(1 << N):
    m = i ^ mm
    j = m
    while 1:
        ans = 0
        for k in RA[i^j^mm]:
            ans += min(DX[k][i], DY[k][j])
        
        pc = PC[i] + PC[j]
        ANS[pc] = min(ANS[pc], ans)
        
        if not j:
            break
        j = m & (j - 1)

print(*ANS, sep = "\n")