Problem:


Score: 500 points

Problem Statement

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

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

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

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

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

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

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

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

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

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

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

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

Constraints

1 \leq N \leq 15

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

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

1 \leq P_i \leq 1 \ 000 \ 000

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer in N+1 lines.

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

Sample Input 1

3
1 2 300
3 3 600
1 4 800

Sample Output 1

2900
900
0
0

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

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

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

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

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

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

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

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

Sample Input 2

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

Sample Output 2

13800
1600
0
0
0
0

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

Sample Input 3

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

Sample Output 3

26700
13900
3200
1200
0
0
0

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

Sample Input 4

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

Sample Output 4

2576709
1569381
868031
605676
366338
141903
0
0
0

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



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


Sample output:
2900
900
0
0

Submission status: Time Limit Exceeded

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

n = int(input())
X, Y, P = [], [], []
T = []
U = 0
for _ in range(n):
    x, y, p = map(int, input().split())
    X.append(x)
    Y.append(y)
    P.append(p)
    t = min(abs(x), abs(y))
    T.append(t)
    U += p*t
X = np.array(X)
Y = np.array(Y)
P = np.array(P)
T = np.array(T)
L = [U]*(n+1)
mask = (1<<n)-1
for i in range(1<<n):
    K = T.copy()
    cnt = 0
    for a, x in enumerate(X):
        if i>>a & 1:
            np.minimum(K, abs(X-x), out=K)
            cnt += 1
    s = i ^ mask
    j = s
    while j:
        M = K.copy()
        temp = cnt
        for b, y in enumerate(Y):
            if j>>b & 1:
                np.minimum(M, abs(Y-y), out=M)
                temp += 1
        if temp <= n:
            L[temp] = min(L[temp], (P*M).sum())
        j = (j-1) & s
    if cnt <= n:
        L[cnt] = min(L[cnt], (P*K).sum())
print(*L, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    X, Y, P = [], [], []
    T = []
    U = 0
    for _ in range(n):
        x, y, p = map(int, input().split())
        X.append(x)
        Y.append(y)
        P.append(p)
        t = min(abs(x), abs(y))
        T.append(t)
        U += p*t
    L = [U]*(n+1)
    mask = (1<<n)-1
    for i in range(1<<n):
        K = T.copy()
        cnt = 0
        for a, x in enumerate(X):
            if i>>a & 1:
                for q in range(n):
                    K[q] = min(K[q], abs(X[q]-x))
                cnt += 1
        s = i ^ mask
        j = s
        while j:
            M = K.copy()
            temp = cnt
            for b, y in enumerate(Y):
                if j>>b & 1:
                    for q in range(n):
                        M[q] = min(M[q], abs(Y[q]-y))
                    temp += 1
            if temp <= n:
                L[temp] = min(L[temp], sum(p*m for p, m in zip(P, M)))
            j = (j-1) & s
        if cnt <= n:
            L[cnt] = min(L[cnt], sum(p*k for p, k in zip(P, K)))
    print(*L, sep="\n")
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

n = int(input())
X, Y, P = [], [], []
T = []
U = 0
for _ in range(n):
    x, y, p = map(int, input().split())
    X.append(x)
    Y.append(y)
    P.append(p)
    t = min(abs(x), abs(y))
    T.append(t)
    U += p*t
L = [U]*(n+1)
mask = (1<<n)-1
for i in range(1<<n):
    K = T.copy()
    cnt = 0
    for a, x in enumerate(X):
        if i>>a & 1:
            for q in range(n):
                K[q] = min(K[q], abs(X[q]-x))
            cnt += 1
    s = i ^ mask
    j = s
    while j:
        M = K.copy()
        temp = cnt
        for b, y in enumerate(Y):
            if j>>b & 1:
                for q in range(n):
                    M[q] = min(M[q], abs(Y[q]-y))
                temp += 1
        if temp <= n:
            L[temp] = min(L[temp], sum(p*m for p, m in zip(P, M)))
        j = (j-1) & s
    if cnt <= n:
        L[cnt] = min(L[cnt], sum(p*k for p, k in zip(P, K)))
print(*L, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    XYP = [tuple(map(int, xyp)) for xyp in map(str.split, args[1:])]
    inf = 10**12
    ret = [inf]*(n+1)

    CH = [[inf]*n for _ in range(2**n)]
    CV = [[inf]*n for _ in range(2**n)]

    for b in range(2**n):
        for src, (sx, sy, p) in enumerate(XYP):
            cx, cy = p*abs(sx), p*abs(sy)
            for i in range(n):
                if not b & (1 << i):
                    continue
                dx, dy, _ = XYP[i]
                cx = min(cx, p*abs(sx-dx))
                cy = min(cy, p*abs(sy-dy))
            CH[b][src] = cy
            CV[b][src] = cx

    for t in range(3**n):
        h, v = 0, 0
        for i in range(n):
            t, r = divmod(t, 3)
            if r == 1:
                h += 1 << i
            elif r == 2:
                v += 1 << i

        cost = 0
        for i in range(n):
            cost += min(CH[h][i], CV[v][i])

        k = bin(h | v).count('1')
        ret[k] = min(ret[k], cost)

    return '\n'.join(map(str, ret))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    XYP = [tuple(map(int, xyp)) for xyp in map(str.split, args[1:])]
    inf = 10**12
    ret = [inf]*(n+1)

    CH = [[inf]*n for _ in range(2**n)]
    CV = [[inf]*n for _ in range(2**n)]

    for b in range(2**n):
        for src, (sx, sy, p) in enumerate(XYP):
            cx, cy = p*abs(sx), p*abs(sy)
            for i in range(n):
                if not b & (1 << i):
                    continue
                dx, dy, _ = XYP[i]
                cx = min(cx, p*abs(sx-dx))
                cy = min(cy, p*abs(sy-dy))
            CH[b][src] = cy
            CV[b][src] = cx

    for b in range(2**n):
        k = bin(b).count('1')
        h = b
        while h+1:
            h &= b
            cost = 0
            for i in range(n):
                cost += min(CH[h][i], CV[b-h][i])

            ret[k] = min(ret[k], cost)
            h -= 1

    return '\n'.join(map(str, ret))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

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):
            s = seq[i][0]
            for j in range(i+1):
                temp = dp[j][0]
                for a, b in seq[:i+1]:
                    temp += min(abs(a), s-a)*b
                dp[j+1][i+1] = min(dp[j+1][i+1], temp)
                temp2 = 10**15
                for k in range(1, i+1):
                    temp = dp[j][k]
                    t = seq[k-1][0]
                    for a, b in seq[k:i+1]:
                        temp += min(abs(a), a-t, s-a)*b
                    temp2 = min(temp2, temp)
                dp[j+1][i+1] = min(dp[j+1][i+1], temp2)
        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):
                t = seq[k-1][0]
                temp = 0
                for a, b in seq[k:m]:
                    temp += min(abs(a), a-t)*b
                dp[i][k] += temp
        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: Time Limit Exceeded

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

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

                    now = min(now,count)
                for j in range(n):
                    dp[r][j+1] = min(dp[r][j+1],dp[l][j]+now)

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

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

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

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

    for i in ans:
        print(i)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

xcal = [[0]*n for i in range(1<<n)]
ycal = [[0]*n for i in range(1<<n)]

for i in range(1<<n):
    for j in range(n):
        xcal[i][j] = abs(l[j][0])
        ycal[i][j] = abs(l[j][1])
        for k in range(n):
            if (i>>k) & 1:
                xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
        xcal[i][j] *= l[j][2]
        ycal[i][j] *= l[j][2]
ans = [float("INF")]*(n+1)

for _ in range(3**n):
    count = 0
    state = _
    x = 0
    y = 0
    for i in range(n):
        if state%3 == 1:
            count += 1
            x += 1<<i
        elif state%3 == 2:
            count += 1
            y += 1<<i
        state //= 3
    z = x|y
    
    cost = 0
    for i in range(n):
        if not (z>>i & 1):
            cost += min(xcal[x][i],ycal[y][i])
        if cost >= ans[count]:
            break
    ans[count] = min(ans[count],cost)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            xcal[i][j] *= l[j][2]
            ycal[i][j] *= l[j][2]
    ans = [float("INF")]*(n+1)

    for _ in range(3**n):
        count = 0
        state = _
        x = 0
        y = 0
        for i in range(n):
            if state%3 == 1:
                count += 1
                x += 1<<i
            elif state%3 == 2:
                count += 1
                y += 1<<i
            state //= 3
        z = x|y
        
        cost = 0
        for i in range(n):
            if not (z>>i & 1):
                cost += min(xcal[x][i],ycal[y][i])
            if cost >= ans[count]:
                break
        ans[count] = min(ans[count],cost)

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            
    ans = [float("INF")]*(n+1)

    for i in range(1<<n):
        count = 0
        for j in range(n):
            if i >> j & 1:
                count += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(n):
                if not (i>>k & 1):
                    cost += min(xcal[j][k],ycal[i-j][k])*l[k][2]
            ans[count] = min(ans[count],cost)
            j -= 1

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

xcal = [[0]*n for i in range(1<<n)]
ycal = [[0]*n for i in range(1<<n)]

for i in range(1<<n):
    for j in range(n):
        xcal[i][j] = abs(l[j][0])
        ycal[i][j] = abs(l[j][1])
        for k in range(n):
            if (i>>k) & 1:
                xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
        
ans = [float("INF")]*(n+1)

for i in range(1<<n):
    count = 0
    for j in range(n):
        if i >> j & 1:
            count += 1
    j = i
    while j >= 0:
        j &= i
        cost = 0
        for k in range(n):
            if not (i>>k & 1):
                cost += min(xcal[j][k],ycal[i-j][k])*l[k][2]
        ans[count] = min(ans[count],cost)
        j -= 1

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

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

xcal = [[0]*n for i in range(1<<n)]
ycal = [[0]*n for i in range(1<<n)]

for i in range(1<<n):
    for j in range(n):
        xcal[i][j] = abs(l[j][0])
        ycal[i][j] = abs(l[j][1])
        for k in range(n):
            if (i>>k) & 1:
                xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
        
ans = [float("INF")]*(n+1)

for i in range(1<<n):
    count = 0
    for j in range(n):
        if i >> j & 1:
            count += 1
    j = i
    while j >= 0:
        j &= i
        cost = 0
        for k in range(n):
            if not (i>>k & 1):
                cost += min(xcal[j][k],ycal[i-j][k])*l[k][2]
        ans[count] = min(ans[count],cost)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

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

xcal = [[0]*n for i in range(1<<n)]
ycal = [[0]*n for i in range(1<<n)]

for i in range(1<<n):
    for j in range(n):
        xcal[i][j] = abs(l[j][0])
        ycal[i][j] = abs(l[j][1])
        for k in range(n):
            if (i>>k) & 1:
                xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
        
ans = [float("INF")]*(n+1)

for i in range(1<<n):
    count = 0
    for j in range(n):
        if i >> j & 1:
            count += 1
    for j in range(i,-1,-1):
        j &= i
        cost = 0
        for k in range(n):
            if not (i>>k & 1):
                cost += min(xcal[j][k],ycal[i-j][k])*l[k][2]
        ans[count] = min(ans[count],cost)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = [float("INF")]*(n+1)

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

xcal = [[0]*n for i in range(1<<n)]
ycal = [[0]*n for i in range(1<<n)]

for i in range(1<<n):
    for j in range(n):
        xcal[i][j] = abs(l[j][0])
        ycal[i][j] = abs(l[j][1])
        for k in range(n):
            if (i>>k) & 1:
                xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
        xcal[i][j] *= l[j][2]
        ycal[i][j] *= l[j][2]

for i in range(1<<n):
    count = 0
    for j in range(n):
        if i >> j & 1:
            count += 1
    for j in range(i,-1,-1):
        j &= i
        cost = 0
        for k in range(n):
            if not (i>>k & 1):
                cost += min(xcal[j][k],ycal[i-j][k])
        ans[count] = min(ans[count],cost)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys


def main():
    N = int( sys.stdin.readline() )
    XYP_list = [ list(map(int, sys.stdin.readline().split())) for _ in range(N) ]

    bit = 1 << N
    x_min = [ [float("inf")]*N for _ in range(bit) ]
    y_min = [ [float("inf")]*N for _ in range(bit) ]


    for b in range(bit):
        for i in range(N):  #  i: current village
            i_x, i_y, i_p = XYP_list[i]
            x_min[b][i] = abs( i_x )
            y_min[b][i] = abs( i_y )

            for j in range(N):  # j: road added
                if b & (1 << j):
                    j_x, j_y, j_p = XYP_list[j]
                    x_min[b][i] = min( x_min[b][i] , abs( i_x - j_x ) )
                    y_min[b][i] = min( y_min[b][i] , abs( i_y - j_y ) )


    ans = [float("inf")] * (N+1)

    for b in range(bit):
        x_bit = b
        y_bit = b - x_bit
        cnt = format(b, 'b').count("1")

        while True:
            cost = 0

            for i in range(N):
                if not (b & (1 << i)):
                    i_x, i_y, i_p = XYP_list[i]
                    cost += min( x_min[x_bit][i] , y_min[y_bit][i]) * i_p
            
            ans[cnt] = min(ans[cnt], cost)

            if (not x_bit):
                break
            
            x_bit = (x_bit - 1) & b
            y_bit = b - x_bit
    

    for v in ans:
        print(v)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    N = int(input())
    l = []
    S = []; X = []; Y = []; P = []
    ans = 0
    for _ in range(N):
        x,y,p = map(int,input().split())
        s = p * min(abs(x),abs(y))
        ans += s
        S.append(s)
        X.append(x); Y.append(y); P.append(p)
    print(ans)
    l_S = []
    for i in range(N*2):
        if i < N:
            x = X[i]
            S_temp = []
            temp = 0
            for j in range(N):
                m = min(S[j],P[j] * (abs(X[j]-x)))
                S_temp.append(m)
                temp += m
            if ans > temp:
                 ans = temp
        else:
            y = Y[i-N]
            S_temp = []
            temp = 0
            for j in range(N):
                m = min(S[j],P[j] * (abs(Y[j]-y)))
                S_temp.append(m)
                temp += m
            if ans > temp:
                 ans = temp
        l_S.append(S_temp)
    print(ans)
    memo = [n for n in range(2 * N)]
    l_S0 = l_S
    for _ in range(N-1):
        l_S1 = []
        newMemo = []
        if ans == 0:
          print(0)
          continue
        for j in range(len(l_S0)):
            for k in range(memo[j]+1, N * 2):
                l = l_S[k]
                l0 = l_S0[j]
                S_temp = []
                temp = 0
                for h in range(N):
                    m = min(l[h],l0[h])
                    S_temp.append(m)
                    temp += m
                if ans > temp:
                     ans = temp
                l_S1.append(S_temp)
                newMemo.append(k)
        memo = newMemo
        l_S0 = l_S1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    N = int(input())
    l = []
    S = []; X = []; Y = []; P = []
    ans = 0
    for _ in range(N):
        x,y,p = map(int,input().split())
        s = p * min(abs(x),abs(y))
        ans += s
        S.append(s)
        X.append(x); Y.append(y); P.append(p)
    print(ans)
    l_S = []
    for i in range(N*2):
        if i < N:
            x = X[i]
            S_temp = []
            temp = 0
            for j in range(N):
                m = min(S[j],P[j] * (abs(X[j]-x)))
                S_temp.append(m)
                temp += m
            if ans > temp:
                 ans = temp
        else:
            y = Y[i-N]
            S_temp = []
            temp = 0
            for j in range(N):
                m = min(S[j],P[j] * (abs(Y[j]-y)))
                S_temp.append(m)
                temp += m
            if ans > temp:
                 ans = temp
        l_S.append(S_temp)
    print(ans)
    memo = [n for n in range(2 * N)]
    l_S0 = l_S
    for _ in range(N-1):
        l_S1 = []
        newMemo = []
        for j in range(len(l_S0)):
            for k in range(memo[j]+1, N * 2):
                l = l_S[k]
                l0 = l_S0[j]
                S_temp = []
                temp = 0
                for h in range(N):
                    m = min(l[h],l0[h])
                    S_temp.append(m)
                    temp += m
                if ans > temp:
                     ans = temp
                l_S1.append(S_temp)
                newMemo.append(k)
        memo = newMemo
        l_S0 = l_S1
        print(ans)

Submission status: Time Limit Exceeded

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

sub=[0]*(1<<n)

for i in range(1, 1<<n):
    arr=[]
    cur=1
    for j in range(n):
        if i&cur>0:
            arr.append(P[j])    
        cur<<=1    
            
    minX, minY=float('inf'), float('inf')        
    for j in range(len(arr)):
        minX_, minY_=0, 0
        baseX, baseY=arr[j][0], arr[j][1]
        for k in range(len(arr)):
            minX_+=abs(arr[k][0]-baseX)*arr[k][2]
            minY_+=abs(arr[k][1]-baseY)*arr[k][2]
        minX=min(minX, minX_)
        minY=min(minY, minY_)
    sub[i]=min(minX, minY)   
    
dp=[[float('inf')]*(1<<n) for _ in range(n+1)]

for i in range(1<<n):
    cur = 1
    S   = 0
    for j in range(n):
        if i&cur>0:
            S+=min(abs(P[j][0]), abs(P[j][1])) * P[j][2]
        cur<<=1    
    dp[0][i]=S        
    
for x in range(1<<n):
    for i in range(x, -1, -1):
        i&=x
        for k in range(1, n+1):
            dp[k][x]=min(dp[k-1][x^i] + sub[i], dp[k][x])    
            
for k in range(n+1):
    print(dp[k][-1])

Submission status: Time Limit Exceeded

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

def solve():
    INF = float('inf')

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

    N2 = 1<<N

    costs = [0] * N2
    for S in range(N2):
        xypSs = []
        for i, (x, y, p) in enumerate(XYPs):
            if (S>>i) & 1:
                xypSs.append((x, y, p))
        cost = INF
        for xR, yR, _ in xypSs:
            c = 0
            for x, y, p in xypSs:
                c += abs(x-xR) * p
            if c < cost:
                cost = c
            c = 0
            for x, y, p in xypSs:
                c += abs(y-yR) * p
            if c < cost:
                cost = c
        costs[S] = cost

    anss = []
    dp = [0] * N2
    for S in range(N2):
        cost = 0
        for i, (x, y, p) in enumerate(XYPs):
            if (S>>i) & 1:
                cost += (abs(x) if abs(x) <= abs(y) else abs(y)) * p
        dp[S] = cost
    anss.append(dp[-1])

    def enumSubset(S):
        subSs = []
        subS = S
        while True:
            subSs.append(subS)
            subS = (subS-1) & S
            if subS == S:
                break
        subSs.reverse()
        return subSs

    for k in range(1, N+1):
        dp2 = [0] * N2
        for S in range(N2):
            subSs = enumSubset(S)
            dp2[S] = min([dp[S-T] + costs[T] for T in subSs])
        dp = dp2
        anss.append(dp[-1])

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


solve()

Submission status: Time Limit Exceeded

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

def solve():
    INF = float('inf')

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

    N2 = 1<<N

    costXss = [[0]*(N) for _ in range(N2)]
    costYss = [[0]*(N) for _ in range(N2)]
    for S in range(N2):
        xySs = []
        for i, (x, y, p) in enumerate(XYPs):
            if (S>>i) & 1:
                xySs.append((x, y))
        costXs = [0] * N
        costYs = [0] * N
        for i, (x, y, p) in enumerate(XYPs):
            c = abs(x)
            for xR, yR in xySs:
                if abs(x-xR) < c:
                    c = abs(x-xR)
            costXs[i] = c * p
            c = abs(y)
            for xR, yR in xySs:
                if abs(y-yR) < c:
                    c = abs(y-yR)
            costYs[i] = c * p
        costXss[S] = costXs
        costYss[S] = costYs

    anss = [INF] * (N+1)
    for ptn in product(range(3), repeat=N):
        bitsetX = bitsetY = 0
        for i in range(N):
            if ptn[i] == 0:
                bitsetX |= 1<<i
            elif ptn[i] == 1:
                bitsetY |= 1<<i

        num1 = bin(bitsetX | bitsetY).count('1')
        ans = 0
        for costX, costY in zip(costXss[bitsetX], costYss[bitsetY]):
            ans += costX if costX <= costY else costY
        if ans < anss[num1]:
            anss[num1] = ans

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


solve()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product


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

INF = 10 ** 6
# INF = float('inf')
dx = [INF] * N
dy = [INF] * N
for i in range(N):
    dx[i] = min(dx[i], abs(T[i][0]))
    dy[i] = min(dy[i], abs(T[i][1]))
tate = [dx * 1 for _ in range(1 << N)]
yoko = [dy * 1 for _ in range(1 << N)]

for bit in product(range(2), repeat=N):
    b = 0
    for i in range(N):
        b += bit[i] * pow(2, (N - 1) - i)
    dx = tate[b]
    dy = yoko[b]
    for i in range(N):
        for j in range(N):
            if bit[i]:
                dx[i] = 0
                dx[j] = min(dx[j], abs(T[i][0] - T[j][0]))
                dy[i] = 0
                dy[j] = min(dy[j], abs(T[i][1] - T[j][1]))

S = [float('inf')] * (N + 1)
for bit in product(range(3), repeat=N):
    k = 0
    x = 0
    y = 0
    p = 1
    for i, b in enumerate(bit):
        if b == 1:
            x += p
            k += 1
        elif b == 2:
            y += p
            k += 1
        p <<= 1
    if S[k] == 0:
        continue
    s = 0
    dx = tate[x]
    dy = yoko[y]
    for i in range(N):
        s += min(dx[i], dy[i]) * T[i][2]
    S[k] = min(S[k], s)

print(*S, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from itertools import product


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

INF = 10 ** 6
# INF = float('inf')
dx = [INF] * N
dy = [INF] * N
for i in range(N):
    dx[i] = min(dx[i], abs(T[i][0]))
    dy[i] = min(dy[i], abs(T[i][1]))
tate = [dx * 1 for _ in range(1 << N)]
yoko = [dy * 1 for _ in range(1 << N)]

for bit in product(range(2), repeat=N):
    b = 0
    for i in range(N):
        b += bit[i] * pow(2, (N - 1) - i)
    dx = tate[b]
    dy = yoko[b]
    for i in range(N):
        for j in range(N):
            if bit[i]:
                dx[i] = 0
                dx[j] = min(dx[j], abs(T[i][0] - T[j][0]))
                dy[i] = 0
                dy[j] = min(dy[j], abs(T[i][1] - T[j][1]))

S = [float('inf')] * (N + 1)
for bit in product(range(3), repeat=N):
    k = 0
    x = 0
    y = 0
    p = 1
    for i, b in enumerate(bit):
        x += p * (b == 1)
        y += p * (b == 2)
        k += (b != 0)
        p <<= 1
    if S[k] == 0:
        continue
    s = 0
    dx = tate[x]
    dy = yoko[y]
    for i in range(N):
        s += min(dx[i], dy[i]) * T[i][2]
    S[k] = min(S[k], s)

print(*S, sep='\n')