Problem:


Score: 500 points

Problem Statement

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

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

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

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

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

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

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

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

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

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

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

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

Constraints

1 \leq N \leq 15

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

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

1 \leq P_i \leq 1 \ 000 \ 000

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer in N+1 lines.

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

Sample Input 1

3
1 2 300
3 3 600
1 4 800

Sample Output 1

2900
900
0
0

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

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

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

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

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

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

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

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

Sample Input 2

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

Sample Output 2

13800
1600
0
0
0
0

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

Sample Input 3

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

Sample Output 3

26700
13900
3200
1200
0
0
0

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

Sample Input 4

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

Sample Output 4

2576709
1569381
868031
605676
366338
141903
0
0
0

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



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


Sample output:
2900
900
0
0

Submission status: Wrong Answer

Solution code:
import sys
from itertools import product
def input(): return sys.stdin.readline().rstrip()


def kyori(dlist, ds):
    return min(map(lambda m: abs(m-ds),dlist))

def main():
    n = int(input())
    li = []
    for _ in range(n):
        xi, yi, pi = map(int, input().split())
        li.append([xi, yi, pi])
    xdist = [[0]*(2**n) for i in range(n)]
    for i in range(2 ** n):
        xlist = [0]
        for j in range(n):
            if ((i >> j) & 1):
                xlist.append(li[j][0])
        for h in range(n):
            xdist[h][i] = kyori(xlist, li[h][0])
    ydist = [[0]*(2**n) for i in range(n)]
    for i in range(2 ** n):
        ylist = [0]
        for j in range(n):
            if ((i >> j) & 1):
                ylist.append(li[j][0])
        for h in range(n):
            ydist[h][i] = kyori(ylist, li[h][1])

    klist = [10**10]*(n+1)
    for xyr in list(product([0, 1, 2], repeat=n)):
        xopen = 0
        yopen = 0
        k = 0
        for index, num in enumerate(xyr):
            xopen += num*(2-num)*2**index
            yopen += (num*(num-1)*2**index)//2
            k += ((num-1)*(2-num)+2)//2
        if klist[k] == 0:
            continue
        cost = 0
        for w in range(n):
            cost += min(xdist[w][xopen], ydist[w][yopen])*li[w][2]

        klist[k] = min(klist[k], cost)

    for g in range(n+1):
        print(klist[g])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations_with_replacement, product
import numpy as np
def input(): return sys.stdin.readline().rstrip()


def kyori(dlist, ds):
    return np.min(np.abs(np.array(dlist)-ds))


def main():
    n = int(input())
    li = []
    for _ in range(n):
        xi, yi, pi = map(int, input().split())
        li.append([xi, yi, pi])
    xdist = [[0]*(2**n) for i in range(n)]
    for i in range(2 ** n):
        xlist = [0]
        for j in range(n):
            if ((i >> j) & 1):
                xlist.append(li[j][0])
        for h in range(n):
            xdist[h][i] = kyori(xlist, li[h][0])
    ydist = [[0]*(2**n) for i in range(n)]
    for i in range(2 ** n):
        ylist = [0]
        for j in range(n):
            if ((i >> j) & 1):
                ylist.append(li[j][0])
        for h in range(n):
            ydist[h][i] = kyori(ylist, li[h][1])

    klist = [10**10]*(n+1)
    for xyr in list(product([0, 1, 2], repeat=n)):
        xopen = 0
        yopen = 0
        k = 0
        for index, num in enumerate(xyr):
            xopen += num*(2-num)*2**index
            yopen += (num*(num-1)*2**index)//2
            k += ((num-1)*(2-num)+2)//2
        if klist[k] == 0:
            continue
        cost = 0
        for w in range(n):
            cost += min(xdist[w][xopen], ydist[w][yopen])*li[w][2]

        klist[k] = min(klist[k], cost)

    for g in range(n+1):
        print(klist[g])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def Base_10_to_n(X, n, m):
    X_dumy = X
    out = ''
    while X_dumy > 0:
        out = str(X_dumy % n) + out
        X_dumy = int(X_dumy / n)
    return "0" * (m - len(out)) + out
    
n = int(input())
date = [list(map(int, input().split())) for i in range(n)]
distance0 = [float("INF")] * n
ans = [float("INF")] * (n + 1)
s = 0
for i in range(n):
    if distance0[i] > min(abs(date[i][0]), abs(date[i][1])):
        distance0[i] = min(abs(date[i][0]), abs(date[i][1]))
        s += distance0[i] * date[i][2]
ans[0] = s


for i in range(3 ** n):
    tri = Base_10_to_n(i, 3, n)
    cnt = 0
    s = ans[0]
    dis = distance0[:]
    for j in range(n):
        if tri[j] == "1":
            for k in range(n):
                if dis[k] > abs(date[j][0] - date[k][0]):
                    s -= (dis[k] - abs(date[j][0] - date[k][0])) * date[k][2]
                    dis[k] = abs(date[j][0] - date[k][0])
            cnt += 1
        elif tri[j] == "2":
            for k in range(n):
                if dis[k] > abs(date[j][1] - date[k][1]):
                    s -= (dis[k] - abs(date[j][1] - date[k][1])) * date[k][2]
                    dis[k] = abs(date[j][1] - date[k][1])
            cnt += 1
    ans[cnt] = min(ans[cnt], s)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import operator


def calc_distance(xyp, x_lines, y_lines):
    return sum(p * min(itertools.chain(
        (abs(x - v) for v in x_lines),
        (abs(y - v) for v in y_lines),
        )) for x, y, p in xyp)


def resolve(in_, out):
    n = int(next(in_))
    xyp = tuple(tuple(map(int, (line.split()))) for line in in_)

    print(calc_distance(xyp, [0], [0]), file=out)

    d = []
    for x in range(-15, 16):
        if x == 0:
            continue
        d.append(calc_distance(xyp, [0, x], [0]))
    for y in range(-15, 16):
        if y == 0:
            continue
        d.append(calc_distance(xyp, [0], [0, y]))
    print(min(d, default=0), file=out)

    x_all_lines = frozenset(('x', x) for x, y, p in xyp if x != 0)
    y_all_lines = frozenset(('y', y) for x, y ,p in xyp if y != 0)
    all_lines = x_all_lines | y_all_lines

    for i in range(2, n + 1):
        d = []
        for lines in itertools.combinations(all_lines, i):
            x_lines = [0]
            y_lines = [0]
            for line in lines:
                if line[0] == 'x':
                    x_lines.append(line[1])
                else:
                    y_lines.append(line[1])
            d.append(calc_distance(xyp, x_lines, y_lines))
        print(min(d, default=0), file=out)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 hogeX(Xlst):
    lst=[]
    for x,y,p in XYP:
        c=idle_max
        for X in Xlst:
            c=min(round(abs(X-x))*p,c)
        lst.append(c)
    return(lst)
def hogeY(Ylst):
    lst=[]
    for x,y,p in XYP:
        c=idle_max
        for Y in Ylst:
            c=min(round(abs(Y-y))*p,c)
        lst.append(c)
    return(lst)

def main(Alst,Blst):
    sumc=0
    for i in range(len(Alst)):
        sumc+=min(Alst[i],Blst[i])
    return (sumc)

def premain(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+1)]
XlstLst=[[] for i in range(N+1)]
YlstLst=[[] for i in range(N+1)]
for bit in product(range(2), repeat=N):
    Xlst=[0]
    Ylst=[0]
    for n in range(N):
        if bit[n]:
            x,y,p=XYP[n]
            Xlst.append(x)
            Ylst.append(y)
    XlstLst[sum(bit)].append(hogeX(Xlst))
    YlstLst[sum(bit)].append(hogeY(Ylst))

#for K in range(N+1):
K=N
for x in range(K+1):
    for Xlst in XlstLst[x]:
        for Ylst in YlstLst[K-x]:
            #print(K)
            scorelst[K]=min(scorelst[K],main(Xlst,Ylst))
scorelst[0]=premain([0],[0])
for score in scorelst:
    print(score)

Submission status: Wrong Answer

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)]
XlstLst=[[] for i in range(N+1)]
YlstLst=[[] for i in range(N+1)]
for bit in product(range(2), repeat=N):
    Xlst=[0]
    Ylst=[0]
    for n in range(N):
        if bit[n]:
            x,y,p=XYP[n]
            Xlst.append(x)
            Ylst.append(y)
    XlstLst[sum(bit)].append(Xlst)
    YlstLst[sum(bit)].append(Ylst)

Submission status: Wrong Answer

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]
        if ans_ == 0:
            for i in range(cnt,n+1):
                ans[i] = 0
            break
        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: Wrong Answer

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f

n = int(input())
date = [list(map(int, input().split())) for i in range(n)]
dis = [float("INF")] * n
s = 0
ans = [float("INF")] * (n + 1)
for i in range(n):
    if dis[i] > min(abs(date[i][0]), abs(date[i][1])):
        dis[i] = min(abs(date[i][0]), abs(date[i][1]))
        s += dis[i] * date[i][2]

ans[0] = s
for i in range(1 << n):
    cnt = popcount(i)
    s = ans[0]
    dis1 = dis[:]
    for j in range(n):
        if i >> j & 1:
            for k in range(2):
                if k == 0:
                    disx = dis1[:]
                    sx = s
                    for m in range(n):
                        if disx[m] > abs(date[j][0] - date[m][0]):
                            sx -= (disx[m] - abs(date[j][0] - date[m][0])) * date[m][2]
                            disx[m] = abs(date[j][0] - date[m][0])
                else:
                    disy = dis1[:]
                    sy = s
                    for m in range(n):
                        if disy[m] > abs(date[j][1] - date[m][1]):
                            sy -= (disy[m] - abs(date[j][1] - date[m][1])) * date[m][2]
                            disy[m] = abs(date[j][1] - date[m][1])
            if sx < sy:
                dis1 = disx[:]
                s = sx
            else:
                dis1 = disy[:]
                s = sy
        ans[cnt] = min(ans[cnt], s)

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

Submission status: Wrong Answer

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)]
N-=1
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: Wrong Answer

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
        for j,(x,y,num) in enumerate(p):
            dxj = abs(x)
            dyj = abs(y)
            for nx in lx:
                nd = abs(x-nx)
                if nd < dxj:
                    dxj = nd
            for ny in ly:
                nd = abs(y-ny)
                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:
            if s == 0:
                for i in range(cnt,n+1):
                    ans[i] = 0
                break
            ans[cnt] = s
    for i in ans:
        print(i)
    return

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

Submission status: Wrong Answer

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:
            if s == 0:
                for i in range(cnt,n+1):
                    ans[i] = 0
                break
            ans[cnt] = s
    for i in ans:
        print(i)
    return

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

Submission status: Wrong Answer

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

for k in range(N+1):
    for bit in list(combinations_with_replacement(range(2), k)):
        Xlst=[0]
        Ylst=[0]
        score=idle_max
        for l in range(len(bit)):
            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[len(bit)]=min(scorelst[len(bit)],_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[len(bit)]=min(scorelst[len(bit)],_score)
                Ylst.append(reY)
        #print(bit,Xlst,Ylst)
scorelst[0]=main([0],[0])
for score in scorelst:
    print(score)

Submission status: Wrong Answer

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 = 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
        ans_ = ans[cnt]
        for i in range(n):
            d = min(dx[i][kx],dy[i][ky])
            s += d
            if s >= ans_:
                break
        else:
            if s == 0:
                for i in range(cnt,n+1):
                    ans[i] = 0
                break
            ans[cnt] = s
    for i in ans:
        print(i)
    return

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

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations_with_replacement, product
import numpy as np
def input(): return sys.stdin.readline().rstrip()


def kyori(xlist, ylist, x, y):
    return min(np.min(np.abs(np.array(xlist)-x)), np.min(np.abs(np.array(ylist)-y)))


def main():
    n = int(input())
    li = []
    for _ in range(n):
        xi, yi, pi = map(int, input().split())
        li.append([xi, yi, pi])
    klist=[10**10]*(n+1)    
    for xyr in list(product([0, 1, 2], repeat=n)):
        nowx=[0]
        nowy=[0]
        for i in range(n):
            if xyr[i] == 1:
                nowx.append(li[i][0])
            elif xyr[i] == 2:
                nowy.append(li[i][1])
        cost=0
        k=len(nowx)+len(nowy)-2
        for lis in li:
            cost += kyori(nowx, nowy, lis[0], lis[1])*lis[2]
        klist[k]=min(klist[k], cost)

    for g in range(n+1):
        print(klist[g])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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(combinations_with_replacement(range(2), 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)