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: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from numba import njit, prange
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in prange(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in prange(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()

Submission status: Accepted

Solution code:
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def cal(xp):
    res=[inf]*(n+1)
    xp.sort()
    m=len(xp)
    dp=[[inf]*(m+1) for _ in range(m+1)]
    dp[0][0]=0
    for l,(x,p) in enumerate(xp):
        dp[l+1][0]=dp[l][0]+abs(x)*p
    for l in range(m):
        dpl=dp[l]
        for r in range(l+1,m+1):
            dpr=dp[r]
            val=inf
            for lx,_ in xp[l:r]:
                cur=0
                for x,p in xp[l:r]:
                    cur+=min(abs(x-lx),abs(x))*p
                val=min(cur,val)
            for j in range(1,m+1):
                dpr[j]=min(dpr[j],dpl[j-1]+val)
    dpm=dp[m]
    for i in range(m+1):res[i]=dpm[i]
    return res

inf = 10 ** 16
n = II()
xyp = LLI(n)
ans=[inf]*(n+1)
for s in range(1<<n):
    xp=[]
    yp=[]
    for i,(x,y,p) in enumerate(xyp):
        if s>>i&1:xp.append((x,p))
        else:yp.append((y,p))
    xc=cal(xp)
    yc=cal(yp)
    for i in range(n+1):
        for j in range(n+1-i):
            ans[i+j]=min(ans[i+j],xc[i]+yc[j])

for a in ans:print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    N = int(input().strip())
    XYP = np.empty((N, 3), dtype=np.int32)
    for i in range(N):
        XYP[i] = np.fromstring(input().strip(), sep=" ")
    return N, XYP


@njit
def solve(N, XYP, INF=10**18):
    ans = np.full(N+1, INF, dtype=np.int64)
    vcost = np.zeros((2**N, N), dtype=np.int32)
    hcost = np.zeros((2**N, N), dtype=np.int32)

    # check 2**N pairs
    for intptn in range(2**N):
        for i in range(N):
            xi, yi, pi = XYP[i]
            v = abs(xi)
            h = abs(yi)
            for j in range(N):
                xj, yj, pj = XYP[j]
                if (intptn >> j) & 1 == 1:
                    v = min(v, abs(xj-xi))
                    h = min(h, abs(yj-yi))
            vcost[intptn, i] += v
            hcost[intptn, i] += h

    # check 3**N pairs
    for intptn in range(3**N):
        # split into two 2**N pairs
        p, intvptn, inthptn = intptn, 0, 0
        u = 0
        for i in range(N):
            if p % 3 == 1:
                intvptn += 1 << (N-i-1)
                u += 1
            elif p % 3 == 2:
                inthptn += 1 << (N-i-1)
                u += 1
            p //= 3
        s = 0
        for i in range(N):
            s += min(vcost[intvptn, i], hcost[inthptn, i]) * XYP[i, 2]
        ans[u] = min(ans[u], s)
    
    return ans


if __name__ == '__main__':
    inputs = read()
    ans = solve(*inputs)
    for a in ans:
        print(a)

Submission status: Accepted

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

xx = [ [ abs(city[j][0]) for j in range(N) ] for i in range(2**N) ]
yy = [ [ abs(city[j][1]) for j in range(N) ] for i in range(2**N) ]

for i in range(2**N):
  X = [0]
  rest = []
  for j in range(N):
    if (i>>j)&1:
      X.append(city[j][0])
      xx[i][j] = 0
    else:
      rest.append(j)

  for j in rest:
    res = 10**15
    for k in X:
      res = min(res, abs(city[j][0]-k))
    xx[i][j] = res

for i in range(2**N):
  Y = [0]
  rest = []
  for j in range(N):
    if (i>>j)&1:
      Y.append(city[j][1])
      yy[i][j] = 0
    else:
      rest.append(j)

  for j in rest:
    res = 10**15
    for k in Y:
      res = min(res, abs(city[j][1]-k))
    yy[i][j] = res


ans = [10**15 for _ in range(N+1)]
for i in range(2**N):
  cond = i
  rest = [j for j in range(N) if (i>>j)&1==0]
  count = N-len(rest)

  while True:
    X = cond
    Y = i-cond
    temp = 0
    for j in rest:
      temp += min(xx[X][j], yy[Y][j])*city[j][2]
    ans[count] = min(ans[count], temp)
    if cond == 0:
      break
    else:
      cond = (cond-1)&i

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

Submission status: Accepted

Solution code:
N=int(input())
city=[]
for i in range(N):
    x,y,p=map(int,input().split())
    city.append((x,y,p))
 
xx=[[abs(city[j][0]) for j in range(N)] for i in range(2**N)]
yy=[[abs(city[j][1]) for j in range(N)] for i in range(2**N)]
 
for i in range(2**N):
    X=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            X.append(city[j][0])
            xx[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in X:
            res=min(res,abs(city[j][0]-k))
        xx[i][j]=res
 
for i in range(2**N):
    Y=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            Y.append(city[j][1])
            yy[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in Y:
            res=min(res,abs(city[j][1]-k))
        yy[i][j]=res
 
ans=[10**15 for i in range(N+1)]
for i in range(2**N):
    cond=i
    rest=[j for j in range(N) if i>>j &1==0]
    count=N-len(rest)
    while True:
        X=cond
        Y=i-cond
        temp=0
        for j in rest:
            temp+=min(xx[X][j],yy[Y][j])*city[j][2]
        ans[count]=min(ans[count],temp)
        if cond==0:
            break
        else:
            cond=(cond-1)&i
 
for i in range(N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    xc = [[0] * n for _ in range(1 << n)]
    yc = [[0] * n for _ in range(1 << n)]
    for s in range(1 << n):
        xcs = xc[s]
        ycs = yc[s]
        for i, (x, y, p) in enumerate(xyp):
            xcost = abs(x)
            ycost = abs(y)
            for j, (lx, ly, _) in enumerate(xyp):
                if s >> j & 1 == 0: continue
                if abs(x - lx) < xcost: xcost = abs(x - lx)
                if abs(y - ly) < ycost: ycost = abs(y - ly)
            xcs[i] = xcost * p
            ycs[i] = ycost * p
    # print(xc)

    ans = [inf] * (n + 1)
    for s in range(1 << n):
        k = bin(s).count("1")
        xs = (1 << n) - 1
        while xs > 0:
            xs &= s
            xcs = xc[xs]
            ycs = yc[s - xs]
            cur = 0
            for i in range(n): cur += min(xcs[i], ycs[i])
            if cur < ans[k]: ans[k] = cur
            xs -= 1

    for a in ans: print(a)

inf = 10 ** 16
n = II()
xyp = LLI(n)

solve()

Submission status: Accepted

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

N=int(input())
P=[list(map(int,input().split())) for i in range(N)]
ANS=[1<<60]*(N+1)
ANS[-1]=0
DP1=[20000]*N

S=0
for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))
    S+=DP1[i]*p

ANS[0]=S

def dfs(DP,now,used):
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x))
            S+=DP2[i]*P[i][2]

        ANS[used+1]=min(ANS[used+1],S)
        dfs(DP2,next_town+1,used+1)

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y))
            S+=DP2[i]*P[i][2]

        ANS[used+1]=min(ANS[used+1],S)
        dfs(DP2,next_town+1,used+1)

dfs(DP1,0,0)

for i in range(1,N):
    ANS[i]=min(ANS[i],ANS[i-1])

print(*ANS)

Submission status: Accepted

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

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

DP1=[20000]*N

S=0
for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))
    S+=DP1[i]*p

ANS[0]=S

def dfs(DP,now,used):
    if used==N-1:
        return
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(DP2,next_town+1,used+1)

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(DP2,next_town+1,used+1)

dfs(DP1,0,0)

for i in range(1,N):
    ANS[i]=min(ANS[i],ANS[i-1])

print(*ANS)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(n, kd, precalc_x, precalc_y):
    ans = np.full(n + 1, 10 ** 18, dtype=np.int64)

    def get_cost(v, bit):
        cost = 0
        pcx = precalc_x[v]
        pcy = precalc_y[v ^ bit]
        for i in range(n):
            cost += min(pcx[i], pcy[i])
        return cost

    for bit in range(1 << n):
        k = kd[bit]
        v = bit
        while v:
            ans[k] = min(ans[k], get_cost(v, bit))
            v = (v - 1) & bit
        ans[k] = min(ans[k], get_cost(0, bit))

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8, i8[:], i8[:,:], i8[:,:])')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8, i8[:], i8[:,:], i8[:,:])', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
n = inp[0]
xxx = inp[1::3]
yyy = inp[2::3]
ppp = inp[3::3]

bit_d = (((np.arange(1 << n)[:, None] & (1 << np.arange(n)))) > 0).astype(np.int64)
precalc_x = abs((xxx[None, :] * bit_d)[..., None] - xxx[None, None, :]).min(axis=1) * ppp[None, :]
precalc_y = abs((yyy[None, :] * bit_d)[..., None] - yyy[None, None, :]).min(axis=1) * ppp[None, :]
kd = bit_d.sum(axis=1)

ans = solve(n, kd, precalc_x, precalc_y)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(n, precalc_x, precalc_y):
    ans = np.full(n + 1, 10 ** 18, dtype=np.int64)

    def get_cost(v, bit):
        cost = 0
        pcx = precalc_x[v]
        pcy = precalc_y[v ^ bit]
        for i in range(n):
            cost += min(pcx[i], pcy[i])
        return cost

    for bit in range(1 << n):
        k = (bit & 0x5555) + (bit >> 1 & 0x5555)
        k = (k & 0x3333) + (k >> 2 & 0x3333)
        k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
        k = (k & 0x00ff) + (k >> 8 & 0x00ff)
        v = bit
        while v:
            ans[k] = min(ans[k], get_cost(v, bit))
            v = (v - 1) & bit
        ans[k] = min(ans[k], get_cost(0, bit))

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8, i8[:,:], i8[:,:])')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8, i8[:,:], i8[:,:])', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
n = inp[0]
xxx = inp[1::3]
yyy = inp[2::3]
ppp = inp[3::3]

bit_d = (((np.arange(1 << n)[:, None] & (1 << np.arange(n)))) > 0).astype(np.int64)
precalc_x = abs((xxx[None, :] * bit_d)[..., None] - xxx[None, None, :]).min(axis=1) * ppp[None, :]
precalc_y = abs((yyy[None, :] * bit_d)[..., None] - yyy[None, None, :]).min(axis=1) * ppp[None, :]

ans = solve(n, precalc_x, precalc_y)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(n, precalc_x, precalc_y):
    ans = np.full(n + 1, 10 ** 18, dtype=np.int64)

    def get_cost(v, bit):
        cost = 0
        pcx = precalc_x[v]
        pcy = precalc_y[v ^ bit]
        for i in range(n):
            if v & (1 << i):
                continue
            cost += min(pcx[i], pcy[i])
        return cost

    for bit in range(1 << n):
        k = (bit & 0x5555) + (bit >> 1 & 0x5555)
        k = (k & 0x3333) + (k >> 2 & 0x3333)
        k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
        k = (k & 0x00ff) + (k >> 8 & 0x00ff)
        v = bit
        while v:
            ans[k] = min(ans[k], get_cost(v, bit))
            v = (v - 1) & bit
        ans[k] = min(ans[k], get_cost(0, bit))

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8, i8[:,:], i8[:,:])')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8, i8[:,:], i8[:,:])', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
n = inp[0]
xxx = inp[1::3]
yyy = inp[2::3]
ppp = inp[3::3]

bit_d = (((np.arange(1 << n)[:, None] & (1 << np.arange(n)))) > 0).astype(np.int64)
precalc_x = abs((xxx[None, :] * bit_d)[..., None] - xxx[None, None, :]).min(axis=1) * ppp[None, :]
precalc_y = abs((yyy[None, :] * bit_d)[..., None] - yyy[None, None, :]).min(axis=1) * ppp[None, :]

ans = solve(n, precalc_x, precalc_y)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(n, kd, precalc_x, precalc_y):
    ans = np.full(n + 1, 10 ** 18, dtype=np.int64)

    for bit in range(1 << n):
        k = kd[bit]
        v = bit
        while v:
            ans[k] = min(ans[k], np.minimum(precalc_x[v], precalc_y[v ^ bit]).sum())
            v = (v - 1) & bit
        ans[k] = min(ans[k], np.minimum(precalc_x[0], precalc_y[bit]).sum())

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8, i8[:], i8[:,:], i8[:,:])')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8, i8[:], i8[:,:], i8[:,:])', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
n = inp[0]
xxx = inp[1::3]
yyy = inp[2::3]
ppp = inp[3::3]

bit_d = (((np.arange(1 << n)[:, None] & (1 << np.arange(n)))) > 0).astype(np.int64)
precalc_x = abs((xxx[None, :] * bit_d)[..., None] - xxx[None, None, :]).min(axis=1) * ppp[None, :]
precalc_y = abs((yyy[None, :] * bit_d)[..., None] - yyy[None, None, :]).min(axis=1) * ppp[None, :]
kd = bit_d.sum(axis=1)

ans = solve(n, kd, precalc_x, precalc_y)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int, readline().split())
xyp = tuple(tuple(map(int, readline().split())) for _ in range(n))

N = 1<<n
INF = 1<<60
resx = []
resy = []
for i in range(n):
    x,y,p = xyp[i]
    rx = [abs(x)]*N
    ry = [abs(y)]*N
    for j in range(n):
        for k in range(1<<j):
            rx[k+(1<<j)] = min(rx[k],abs(x-xyp[j][0]))
            ry[k+(1<<j)] = min(ry[k],abs(y-xyp[j][1]))
    
    for j in range(N):
        rx[j] *= p
        ry[j] *= p
    resx.append(rx)
    resy.append(ry)

cnt = [n]*N
for j in range(n):
    for k in range(1<<j):
        cnt[k+(1<<j)] = cnt[k]-1

ans = [INF]*(n+1)
for m0 in range(N):
    v = cnt[m0]
    mx = (N-1)&~m0
    while mx>=0:
        my = (N-1)^m0^mx
        r = 0    
        for i in range(n):
            if m0>>i&1:
                r += min(resx[i][mx],resy[i][my])
        if r < ans[v]:
            ans[v] = r
        mx = (mx-1)&~m0


for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys

n, *towns = map(int, sys.stdin.buffer.read().split())
xxx = towns[0::3]
yyy = towns[1::3]
ppp = towns[2::3]

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

precalc_dist_x = []
precalc_dist_y = []
for bit in range(1 << n):
    dists_x = []
    dists_y = []
    for i in range(n):
        x = xxx[i]
        y = yyy[i]
        dist_x = abs(x)
        dist_y = abs(y)

        t = bit
        j = 0
        while t:
            if t & 1:
                dist_x = min(dist_x, abs(xxx[j] - x))
                dist_y = min(dist_y, abs(yyy[j] - y))
            t >>= 1
            j += 1
        dists_x.append(dist_x * ppp[i])
        dists_y.append(dist_y * ppp[i])
    precalc_dist_x.append(dists_x)
    precalc_dist_y.append(dists_y)

for bit in range(1 << n):
    k = (bit & 0x5555) + (bit >> 1 & 0x5555)
    k = (k & 0x3333) + (k >> 2 & 0x3333)
    k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
    k = (k & 0x00ff) + (k >> 8 & 0x00ff)
    vertical = bit
    while vertical:
        cost = 0
        pcx = precalc_dist_x[vertical]
        pcy = precalc_dist_y[vertical ^ bit]
        for i in range(n):
            cost += min(pcx[i], pcy[i])
        ans[k] = min(ans[k], cost)
        vertical = (vertical - 1) & bit
    cost = 0
    pcx = precalc_dist_x[0]
    pcy = precalc_dist_y[bit]
    for i in range(n):
        cost += min(pcx[i], pcy[i])
    ans[k] = min(ans[k], cost)

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int, readline().split())
xyp = tuple(tuple(map(int, readline().split())) for _ in range(n))

N = 1<<n
INF = 1<<60
resx = []
resy = []
for i in range(n):
    x,y,p = xyp[i]
    rx = [min(abs(x),abs(y))]*N
    ry = [min(abs(x),abs(y))]*N
    for j in range(n):
        for k in range(1<<j):
            rx[k+(1<<j)] = min(rx[k],abs(x-xyp[j][0]))
            ry[k+(1<<j)] = min(ry[k],abs(y-xyp[j][1]))
    
    for j in range(N):
        rx[j] *= p
        ry[j] *= p
    resx.append(rx)
    resy.append(ry)

ans = [INF]*(n+1)
N = 3**n

p = tuple(3**i for i in range(n+1))
rv = [0]*N
rx = [0]*N
ry = [0]*N
for j in range(n):
    for k in range(p[j]):
        rv[k+  p[j]] = rv[k+2*p[j]] = rv[k]
        rv[k] += 1

        rx[k+  p[j]] = rx[k]|(1<<j)
        ry[k+  p[j]] = ry[k]

        rx[k+2*p[j]] = rx[k]
        ry[k+2*p[j]] = ry[k]|(1<<j)

for mask in range(N):
    v = rv[mask]
    x = rx[mask]
    y = ry[mask]
    
    r = 0    
    for i in range(n):
        r += min(resx[i][x],resy[i][y])
    if r < ans[v]:
        ans[v] = r

for i in ans[::-1]:
    print(i)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    xyp = [list(map(int, input().split())) for _ in [0]*n]
    d = []

    def calc(seq):
        m = len(seq)
        dp = [[10**15]*(m+1) for _ in [0]*(m+1)]
        dp[0][0] = 0
        for i in range(m):
            for j in range(i+1):
                temp = dp[j][0]
                for a, b in seq[:i+1]:
                    temp += min(abs(a), seq[i][0]-a)*b
                dp[j+1][i+1] = min(dp[j+1][i+1], temp)
                for k in range(1, i+1):
                    temp = dp[j][k]
                    for a, b in seq[k:i+1]:
                        temp += min(abs(a), a-seq[k-1][0], seq[i][0]-a)*b
                    dp[j+1][i+1] = min(dp[j+1][i+1], temp)
        for i in range(m+1):
            for a, b in seq[:m]:
                dp[i][0] += abs(a)*b
            for k in range(1, m+1):
                for a, b in seq[k:m]:
                    dp[i][k] += min(abs(a), a-seq[k-1][0])*b
        for i in range(m+1):
            dp[i] = min(dp[i])
        dp += [0]*(n-m)
        return dp

    xyp.sort()
    for i in range(2**n):
        x_list, y_list = [], []
        for j in range(n):
            x, y, p = xyp[j]
            if i & 1:
                x_list.append([x, p])
            else:
                y_list.append([y, p])
            i >>= 1
        y_list.sort()
        d.append([calc(x_list), calc(y_list)])

    ans = [10**15]*(n+1)
    for x, y in d:
        for i in range(n+1):
            for j in range(n-i+1):
                ans[i+j] = min(ans[i+j], x[i]+y[j])
    for i in ans:
        print(i)


main()

Submission status: Accepted

Solution code:
N = int(input())
X = []; Y = []; P = []
INF = float("inf")
for i in range(N):
  x,y,p = list(map(int,input().split()))
  X.append(x);Y.append(y);P.append(p)
ans = [INF for _ in range(N+1)] #0本置いた時からN本置いた時までN+1個

def calc(A):
  n = len(A) #Aにはいくつ入っているか。つまり、xoryで選ばれたものはいくつあるか。
  A.sort()
  dp = [[INF]*(n+1) for _ in range(n+1)] #i個目までカバーしてj個目まで道を置いた。
  dp[0][0] = 0
  for l in range(n):
    for r in range(l+1,n+1):
      now = INF
      for k in range(l,r):
        s = 0
        for i in range(l,r):
          s += abs(A[i][0]-A[k][0])*A[i][1]
        now = min(now,s)
      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 = [INF for _ in range(n+1)] #道が0本からn本
  for j in range(n+1):
    res[j] = dp[n][j]

  return res
    

for s in range(1<<N): #x軸にするかをbitで全探索
  AX = [];AY = [] #Aは選ばれた村を追加していく。2**N回これは更新される。
  for i in range(N):
    if (s>>i)&1 == 1: #x軸で見る
      AX.append((X[i],P[i]))
    else:
      AY.append((Y[i],P[i]))
    
  dx = calc(AX)
  dy = calc(AY)
  for i in range(len(dx)):
    for j in range(len(dy)):
      ans[i+j] = min(ans[i+j],dx[i]+dy[j])
for t in ans:
  print(t)

Submission status: Accepted

Solution code:
import sys

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

bits = 1 << N

xmemo = [sys.maxsize]*(N*bits)
ymemo = [sys.maxsize]*(N*bits)

for b in range(bits):
  for i in range(N):
    xmemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][0]), xmemo[b*N+i])
    ymemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][1]), ymemo[b*N+i])
    if not (b & (1<<i)):
      continue
    for j in range(N):
      xmemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][0]-XYP[j][0]), xmemo[b*N+j])
      ymemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][1]-XYP[j][1]), ymemo[b*N+j])
      
ans = [sys.maxsize]*(N+1)

for b in range(bits):
  b_ = b
  cnt = bin(b_).count('1')
  while b_ >= 0:
    b_ &= b
    yi = b - b_
    tmp = 0
    for i in range(N):
      tmp += min(xmemo[b_*N+i], ymemo[yi*N+i])
    ans[cnt] = min(ans[cnt], tmp)
    b_ -= 1
  
for i in range(N+1):
  print(ans[i])

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    xyp = [list(map(int, input().split())) for _ in [0]*n]
    d = []

    def calc(seq):
        m = len(seq)
        dp = [[0] for _ in [0]*1]  # 使った回数、前のやつ
        for i in range(m):
            dp2 = [[10**15]*(i+2) for _ in [0]*(i+2)]
            for j in range(i+1):
                for k in range(i+1):
                    dp2[j][k] = min(dp2[j][k], dp[j][k])
                    temp = dp[j][k]
                    if k == 0:
                        for l in range(k, i+1):
                            temp += min(abs(seq[l][0]), seq[i]
                                        [0]-seq[l][0])*seq[l][1]
                    else:
                        for l in range(k, i+1):
                            temp += min(abs(seq[l][0]), seq[l]
                                        [0]-seq[k-1][0], seq[i][0]-seq[l][0])*seq[l][1]
                    dp2[j+1][i+1] = min(dp2[j+1][i+1], temp)
            dp = dp2
        for i in range(m+1):
            for l in range(m):
                dp[i][0] += abs(seq[l][0])*seq[l][1]
            for k in range(1, m+1):
                for l in range(k, m):
                    dp[i][k] += min(abs(seq[l][0]), seq[l]
                                    [0]-seq[k-1][0])*seq[l][1]
        for i in range(m+1):
            dp[i] = min(dp[i])
        dp += [0]*(n-m)
        return dp

    xyp.sort()
    for i in range(2**n):
        x_list, y_list = [], []
        for j in range(n):
            x, y, p = xyp[j]
            if i & 1:
                x_list.append([x, p])
            else:
                y_list.append([y, p])
            i >>= 1
        y_list.sort()
        d.append([calc(x_list), calc(y_list)])

    ans = [10**15]*(n+1)
    for x, y in d:
        for i in range(n+1):
            for j in range(n-i+1):
                ans[i+j] = min(ans[i+j], x[i]+y[j])
    for i in ans:
        print(i)


main()