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:
# 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)


ans = [INF]*(n+1)
for m0 in range(N):
    v = n
    for i in range(n):
        if m0>>i&1: v-=1
    mx = (N-1)&~m0
    while mx>=0:
        my = (N-1)^m0^mx
        r = 0    
        for i in range(n):
            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: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    P = read_lists(N)

    C = [10 ** 12] * (N + 1)
    CX = [[0] * N for _ in range(2 ** N)]
    CY = [[0] * N for _ in range(2 ** N)]
    LX = [0] * (2 ** N)
    LY = [0] * (2 ** N)
    for T in range(2 ** N):
        X = {0}
        Y = {0}
        S = set()
        for i in range(N):
            if (T >> i) & 1:
                X.add(P[i][0])
                Y.add(P[i][1])
                S.add(i)

        for j, (xp, yp, _) in enumerate(P):
            if j in S:
                continue
            CX[T][j] = min(abs(xp - x) for x in X)
            CY[T][j] = min(abs(yp - y) for y in Y)
        LX[T] = len(X)
        LY[T] = len(Y)

    for T in itertools.product((0, 1, 2), repeat=N):
        tx = 0
        ty = 0
        for i, t in enumerate(T):
            if t == 1:
                tx |= (1 << i) 
            elif t == 2:
                ty |= (1 << i) 

        c = 0
        for n in range(N):
            c += min(CX[tx][n], CY[ty][n]) * P[n][2]
        p = LX[tx] + LY[ty] - 2
        C[p] = min(C[p], c)

    print("\n".join(map(str, C)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

default_dist = [min(abs(x), abs(y)) for x, y, p in towns]

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)
    i = 0
    t = bit
    selected = []
    is_selected = [False] * n
    while t:
        if t & 1:
            selected.append(towns[i])
            is_selected[i] = True
        t >>= 1
        i += 1

    for bit2 in range(1 << k):
        cost = 0
        for i in range(n):
            if is_selected[i]:
                continue
            town_dist = default_dist[i]
            t = bit2
            x, y, p = towns[i]
            for j in range(k):
                if t & 1:
                    town_dist = min(town_dist, abs(selected[j][1] - y))
                else:
                    town_dist = min(town_dist, abs(selected[j][0] - x))
                t >>= 1
            cost += town_dist * p
        ans[k] = min(ans[k], cost)

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    P = read_lists(N)

    C = [10 ** 12] * (N + 1)
    CX = [[0] * N for _ in range(2 ** N)]
    CY = [[0] * N for _ in range(2 ** N)]
    LX = [0] * (2 ** N)
    LY = [0] * (2 ** N)
    for T in range(2 ** N):
        X = {0}
        Y = {0}
        for i in range(N):
            if (T >> i) & 1:
                X.add(P[i][0])
                Y.add(P[i][1])

        for j, (xp, yp, _) in enumerate(P):
            CX[T][j] = min(abs(xp - x) for x in X)
            CY[T][j] = min(abs(yp - y) for y in Y)
        LX[T] = len(X)
        LY[T] = len(Y)

    for T in itertools.product(range(3), repeat=N):
        tx = 0
        ty = 0
        for i, t in enumerate(T):
            if t == 1:
                tx |= (1 << i) 
            elif t == 2:
                ty |= (1 << i) 

        c = 0
        for n in range(N):
            c += min(CX[tx][n], CY[ty][n]) * P[n][2]
        p = LX[tx] + LY[ty] - 2
        C[p] = min(C[p], c)

    print("\n".join(map(str, C)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    P = read_lists(N)

    C = [10 ** 12] * (N + 1)
    CX = [[0] * N for _ in range(2 ** N)]
    CY = [[0] * N for _ in range(2 ** N)]
    SX = [{0} for _ in range(2 ** N)]
    SY = [{0} for _ in range(2 ** N)]
    for T in range(2 ** N):
        for i in range(N):
            if (T >> i) & 1:
                SX[T].add(P[i][0])
                SY[T].add(P[i][1])

        for j, (xp, yp, _) in enumerate(P):
            CX[T][j] = min(abs(xp - x) for x in SX[T])
            CY[T][j] = min(abs(yp - y) for y in SY[T])

    LX = [0] * (2 ** N)
    LY = [0] * (2 ** N)
    for i, (sx, sy) in enumerate(zip(SX, SY)):
        LX[i] = len(sx)
        LY[i] = len(sy)

    for T in itertools.product(range(3), repeat=N):
        tx = 0
        ty = 0
        for i, t in enumerate(T):
            if t == 1:
                tx |= (1 << i) 
            elif t == 2:
                ty |= (1 << i) 

        c = 0
        for n in range(N):
            c += min(CX[tx][n], CY[ty][n]) * P[n][2]
        p = LX[tx] + LY[ty] - 2
        C[p] = min(C[p], c)

    print("\n".join(map(str, C)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from itertools import product
ans = [INF]*(n+1)
for lst in product(range(3),repeat=n):
    """
    0: なし、1: 縦、2: 横
    """
    v = lst.count(0)
    x = y = 0
    for i in range(n):
        if lst[i]==1: x |= 1<<i
        if lst[i]==2: y |= 1<<i
    
    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: Time Limit Exceeded

Solution code:
from itertools import product
from bisect import bisect
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():
    itox = list(sorted(set([x for x, y, p in xyp])))
    xtoi = {x: i for i, x in enumerate(itox)}
    xc = [[0] * (1 << len(itox)) for _ in range(n)]
    for bit in range(1 << len(itox)):
        xx = [-inf]
        for i in range(len(itox)):
            if bit >> i & 1: xx.append(itox[i])
        xx.append(inf)
        for i, (x, y, p) in enumerate(xyp):
            j = bisect(xx, x)
            xc[i][bit] = min(x - xx[j - 1], xx[j] - x, abs(x)) * p
    # print(itox)
    # p2D(xc)

    itoy = list(sorted(set([y for x, y, p in xyp])))
    ytoi = {y: i for i, y in enumerate(itoy)}
    yc = [[0] * (1 << len(itoy)) for _ in range(n)]
    for bit in range(1 << len(itoy)):
        yy = [-inf]
        for i in range(len(itoy)):
            if bit >> i & 1: yy.append(itoy[i])
        yy.append(inf)
        for i, (x, y, p) in enumerate(xyp):
            j = bisect(yy, y)
            yc[i][bit] = min(y - yy[j - 1], yy[j] - y, abs(y)) * p

    # print(itoy)
    # p2D(yc)

    def chmin(i, val): ans[i] = min(ans[i], val)

    ans = [inf] * (n + 1)
    for aa in product(range(3), repeat=n):
        xb = yb = 0
        cl = 0
        for a, (x, y, p) in zip(aa, xyp):
            if a == 1: xb |= 1 << xtoi[x]
            if a == 2: yb |= 1 << ytoi[y]
            if a: cl += 1
        chmin(cl, sum(min(xc[i][xb], yc[i][yb]) for i in range(n)))

    for i in range(n):
        if ans[i] == inf: ans[i] = 0

    for a in ans: print(a)

inf=10**16
n=II()
xyp=[]
for _ in range(n):
    x,y,p=MI()
    if x*y==0:continue
    xyp.append((x,y,p))

solve()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    P = read_lists(N)

    C = [10 ** 12] * (N + 1)
    CX = [[0 for _ in range(N)] for _ in range(2 ** N)]
    CY = [[0 for _ in range(N)] for _ in range(2 ** N)]
    SX = [{0} for _ in range(2 ** N)]
    SY = [{0} for _ in range(2 ** N)]
    for T in range(2 ** N):
        for i in range(N):
            if (T >> i) & 1:
                SX[T].add(P[i][0])
                SY[T].add(P[i][1])

        for j, (xp, yp, _) in enumerate(P):
            CX[T][j] = min(abs(xp - x) for x in SX[T])
            CY[T][j] = min(abs(yp - y) for y in SY[T])

    for T in itertools.product(range(3), repeat=N):
        tx = 0
        ty = 0
        for i, t in enumerate(T):
            if t == 1:
                tx |= (1 << i) 
            elif t == 2:
                ty |= (1 << i) 

        c = 0
        for n in range(N):
            c += min(CX[tx][n], CY[ty][n]) * P[n][2]
        p = len(SX[tx]) + len(SY[ty]) - 2
        C[p] = min(C[p], c)

    print("\n".join(map(str, C)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product,count

def solve(A):
    min2 = lambda x,y: x if x < y else y
    N = len(A)
    vert = [None]*(N * 2**N)
    hori = [None]*(N * 2**N)
    i = 0
    for comb in range(1 << N):
        b = bin(comb|(1 << N))[3:]
        b = [c == "1" for c in b]
        for x,y,p in A:
            mx = abs(x)
            my = abs(y)
            for f,(x2,y2,_) in zip(b,A):
                if f:
                    mx = min2(mx, abs(x-x2))
                    my = min2(my, abs(y-y2))
            vert[i] = mx*p
            hori[i] = my*p
            i += 1

    vert = tuple(vert)
    hori = tuple(hori)

    def score(comb):
        vi = 0
        hi = 0
        pop = 0
        for x in comb:
            vi <<= 1
            hi <<= 1
            if x == 0:
                continue
            if x == 1:
                vi |= 1
            else:
                hi |= 1
            pop += 1
        return pop, sum(map(min2,vert[vi*N:(vi+1)*N],hori[hi*N:(hi+1)*N]))


    res = [float('inf')]*(N+1)
    for i,comb in enumerate(product(range(3), repeat=N)):
        pop, s = score(comb)
        res[pop] = min2(res[pop], s)

    return res



if __name__ == '__main__':
    N = int(input())
    A = [tuple(map(int,input().split())) for _ in range(N)]
    print(*solve(A), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    P = read_lists(N)

    C = [V(min) for _ in range(N + 1)]
    CX = [[0 for _ in range(N)] for _ in range(2 ** N)]
    CY = [[0 for _ in range(N)] for _ in range(2 ** N)]
    SX = [{0} for _ in range(2 ** N)]
    SY = [{0} for _ in range(2 ** N)]
    for T in range(2 ** N):
        for i in range(N):
            if (T >> i) & 1:
                SX[T].add(P[i][0])
                SY[T].add(P[i][1])

        for j, (xp, yp, _) in enumerate(P):
            CX[T][j] = min(abs(xp - x) for x in SX[T])
            CY[T][j] = min(abs(yp - y) for y in SY[T])


    for T in itertools.product(range(3), repeat=N):
        tx = 0
        ty = 0
        for i, t in enumerate(T):
            if t == 1:
                tx |= (1 << i) 
            elif t == 2:
                ty |= (1 << i) 
            
        c = 0
        for n in range(N):
            c += min(CX[tx][n], CY[ty][n]) * P[n][2]
        C[len(SX[tx]) + len(SY[ty]) - 2].ud(c)

    print("\n".join(map(str, C)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product,count

def solve(A):
    min2 = lambda x,y: x if x < y else y
    N = len(A)
    vert = [None]*(N * 2**N)
    hori = [None]*(N * 2**N)
    iit = count()
    for comb in range(1 << N):
        b = bin(comb|(1 << N))[3:]
        b = [c == "1" for c in b]
        for (x,y,p),i in zip(A,iit):
            mx = abs(x)
            my = abs(y)
            for f,(x2,y2,_) in zip(b,A):
                if f:
                    mx = min2(mx, abs(x-x2))
                    my = min2(my, abs(y-y2))
            vert[i] = mx*p
            hori[i] = my*p


    def score(comb):
        vi = 0
        hi = 0
        pop = 0
        for _ in range(N):
            n = comb%3
            pop += (n != 0)
            vi = (vi << 1)|(n == 2)
            hi = (hi << 1)|(n == 1)
            comb //= 3
        return pop, sum(min2(x,y) for x,y in zip(vert[vi*N:(vi+1)*N], hori[hi*N:(hi+1)*N]))


    res = [float('inf')]*(N+1)
    for comb in range(3**N):
        pop, s = score(comb)
        res[pop] = min2(res[pop], s)

    return res



if __name__ == '__main__':
    N = int(input())
    A = [tuple(map(int,input().split())) for _ in range(N)]
    print(*solve(A), sep='\n')

Submission status: Time Limit Exceeded

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): #r-1個目をカバーするのにj個目をl~rのどこに置くのがよいか。
      now = INF
      for k in range(l,r): #位置kに置いたとして
        s = 0
        for i in range(l,r): #l~r-1のすべての点とkとの距離を足し算
          s += abs(A[i][0]-A[k][0])*A[i][1]
        now = min(now,s)
      for j in range(n): #l-1個目からr個目をカバーするときに道を一個増やしたときの最小値
        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: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    P = read_lists(N)

    C = [V(min) for _ in range(N + 1)]
    CX = [[0 for _ in range(N)] for _ in range(2 ** N)]
    CY = [[0 for _ in range(N)] for _ in range(2 ** N)]
    for T in range(2 ** N):
        X = {0}
        Y = {0}
        for i in range(N):
            if (T >> i) & 1:
                X.add(P[i][0])
                Y.add(P[i][1])

        for j, (xp, yp, _) in enumerate(P):
            CX[T][j] = min(abs(xp - x) for x in X)
            CY[T][j] = min(abs(yp - y) for y in Y)

    for T in itertools.product(range(3), repeat=N):
        X = {0}
        Y = {0}
        tx = 0
        ty = 0
        for i, t in enumerate(T):
            if t == 1:
                X.add(P[i][0])
                tx += (1 << i) 
            elif t == 2:
                Y.add(P[i][1])
                ty += (1 << i) 
            
        c = 0
        for n in range(N):
            c += min(CX[tx][n], CY[ty][n]) * P[n][2]
    
        C[len(X) + len(Y) - 2].ud(c)

    print("\n".join(map(str, C)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, queue, math, copy, itertools, bisect, collections, heapq


def main():
    INF = 10 ** 15
    LI = lambda: [int(x) for x in sys.stdin.readline().split()]
    NI = lambda: int(sys.stdin.readline())

    N = NI()
    X = []
    Y = []
    P = []

    for _ in range(N):
        a, b, c = LI()
        X.append(a)
        Y.append(b)
        P.append(c)

    r = []
    for a, b, c in zip(X, Y, P):
        r.append(min(abs(a), abs(b)) * c)

    hor = [copy.copy(r) for _ in range(2 ** N)]
    ver = [copy.copy(r) for _ in range(2 ** N)]

    for i in range(2 ** N):
        k = i
        for b in range(N):
            if k % 2 == 1:
                for j in range(N):
                    hor[i][j] = min(hor[i][j], abs(X[j] - X[b]) * P[j])
                    ver[i][j] = min(ver[i][j], abs(Y[j] - Y[b]) * P[j])
            k //= 2

    ans = [INF] * (N + 1)
    for i in range(3 ** N):
        cnt:int = 0
        bx:int = 0
        by:int = 0
        for b in range(N):
            bx <<= 1
            by <<= 1
            if i % 3 == 1:
                bx += 1
                cnt += 1
            elif i % 3 == 2:
                by += 1
                cnt += 1
            i //= 3
        if ans[cnt] == 0: continue
        s:int = 0
        for b in range(N):
            s += min(hor[bx][b], ver[by][b])
        ans[cnt] = min(ans[cnt], s)
        if ans[cnt] == 0:
            for j in (cnt,N+1):
                ans[cnt] = 0

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

xcost = [[0]*(1<<len(xl)) for _ in range(N)]
ycost = [[0]*(1<<len(yl)) for _ in range(N)]
for i,(x,y,p) in enumerate(XYP):
    for b in range(1<<len(xl)):
        d = abs(x)
        for k in range(len(xl)):
            if b&(1<<k):
                d = min(d, abs(x - xl[k]))
        xcost[i][b] = d*p
    for b in range(1<<len(yl)):
        d = abs(y)
        for k in range(len(yl)):
            if b&(1<<k):
                d = min(d, abs(y - yl[k]))
        ycost[i][b] = d*p

xk = [[] for _ in range(N+1)]
yk = [[] for _ in range(N+1)]
for b in range(1<<len(xl)):
    c = bin(b).count('1')
    if c > N: continue
    xk[c].append(b)
for b in range(1<<len(yl)):
    c = bin(b).count('1')
    if c > N: continue
    yk[c].append(b)

for k in range(N+1):
    if k >= len(xl) or k >= len(yl):
        print(0)
        continue
    ans = 10**20
    for xc in range(k+1):
        yc = k-xc
        for xb in xk[xc]:
            for yb in yk[yc]:
                cost = 0
                for i in range(N):
                    cost += min(xcost[i][xb], ycost[i][yb])
                    if cost >= ans: break
                else:
                    ans = min(ans, cost)
    print(ans)

Submission status: Time Limit Exceeded

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)

pos = 3**N
for t in range(pos):
  l = []
  for _ in range(N):
    l.append(t%3)
    t //= 3
  xi = 0
  yi = 0
  cnt = 0
  for i in range(N):
    if l[i] == 0:
      xi += 1 << i
      cnt += 1
    elif l[i] == 1:
      yi += 1 << i
      cnt += 1
  tmp = 0
  for i in range(N):
    tmp += min(xmemo[xi*N+i], ymemo[N*yi+i])
  ans[cnt] = min(ans[cnt], tmp)
  
  
for i in range(N+1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys, queue, math, copy, itertools, bisect, collections, heapq


def main():
    INF = 10 ** 15
    LI = lambda: [int(x) for x in sys.stdin.readline().split()]
    NI = lambda: int(sys.stdin.readline())

    N = NI()
    X = []
    Y = []
    P = []

    for _ in range(N):
        a, b, c = LI()
        X.append(a)
        Y.append(b)
        P.append(c)

    r = []
    for a, b, c in zip(X, Y, P):
        r.append(min(abs(a), abs(b)) * c)

    hor = [copy.copy(r) for _ in range(2 ** N)]
    ver = [copy.copy(r) for _ in range(2 ** N)]

    for i in range(2 ** N):
        k = i
        for b in range(N):
            if k % 2 == 1:
                for j in range(N):
                    hor[i][j] = min(hor[i][j], abs(X[j] - X[b]) * P[j])
                    ver[i][j] = min(ver[i][j], abs(Y[j] - Y[b]) * P[j])
            k //= 2

    ans = [INF] * (N + 1)
    for i in range(3 ** N):
        cnt:int = 0
        bx:int = 0
        by:int = 0
        for b in range(N):
            bx <<= 1
            by <<= 1
            if i % 3 == 1:
                bx += 1
                cnt += 1
            elif i % 3 == 2:
                by += 1
                cnt += 1
            i //= 3
        if ans[cnt] == 0: continue
        s:int = 0
        for b in range(N):
            s += min(hor[bx][b], ver[by][b])
        ans[cnt] = min(ans[cnt], s)

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


if __name__ == '__main__':
    main()

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 = [[0]]
        for i in range(m):
            dp2 = [[10**15]*(i+2) for _ in [0]*(i+2)]
            for j in range(i+1):
                dp2[j][0] = min(dp2[j][0], dp[j][0])
                temp = dp[j][0]
                for a, b in seq[:i+1]:
                    temp += min(abs(a), seq[i][0]-a)*b
                dp2[j+1][i+1] = min(dp2[j+1][i+1], temp)
                for k in range(1, i+1):
                    dp2[j][k] = min(dp2[j][k], dp[j][k])
                    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
                    dp2[j+1][i+1] = min(dp2[j+1][i+1], temp)
            dp = dp2
        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()