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
from itertools import combinations
input = sys.stdin.buffer.readline
N = int(input())
cities = []
for _ in range(N):
    X, Y, P = map(int, input().split())
    cities.append((X, Y, P))
# print(f'{cities}')


def f(x0, y0, x1, y1, x2, y2):
    a = x2 - x1
    b = y2 - y1
    a2 = a * a
    b2 = b * b
    r2 = a2 + b2
    tt = -(a * (x1 - x0) + b * (y1 - y0))
    if tt < 0:
        return (x2 - x0) * (x2 - x0) + (y2 - y0) * (y2 - y0)
    f1 = a * (y1 - y0) - b * (x1 - x0)
    return (f1 * f1) / r2


MARGIN = 30000

XY = []
for i in range(N * 2):
    x, y, p = cities[i % N]
    if i < N:
        # yoko
        x1, y1 = x - MARGIN, y
        x2, y2 = x + MARGIN, y
        XY.append((x1, y1, x2, y2))
    else:
        # tate
        x1, y1 = x, y - MARGIN
        x2, y2 = x, y + MARGIN
        XY.append((x1, y1, x2, y2))
XY.append((-MARGIN, 0, MARGIN, 0))
XY.append((0, -MARGIN, 0, MARGIN))

S = 10**50
for K in range(N):
    gt = combinations(range(N * 2), K)
    for combi in gt:
        # print(f'{combi=}')
        do = True
        for i in range(len(combi) - 1):
            for j in range(i + 1, len(combi)):
                if combi[i] + N == combi[j]:
                    do = False
                    break
            if not do:
                break
        if not do:
            # print(f'continue {combi}')
            continue
        # print(f'end {combi=}')

        _S = 0
        for i in range(N):
            x0, y0, p = cities[i]
            d = 10**20
            for j in combi:
                x1, y1, x2, y2 = XY[j]
                d = min(d, f(x0, y0, x1, y1, x2, y2))
            # print(f'd={round(d**0.5)}')
            x1, y1, x2, y2 = XY[-2]
            d = min(d, f(x0, y0, x1, y1, x2, y2))
            x1, y1, x2, y2 = XY[-1]
            d = min(d, f(x0, y0, x1, y1, x2, y2))
            _S += round(d**0.5) * p
        S = min(S, _S)
        # print(f'{S=}')
    # print(f'for out {S=}')
    print(S)
    if S == 0:
        # print('test')
        for i in range(N - K):
            print(0)
        exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:

def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


def main():
    from itertools import combinations
    import bisect
    N = int(input())
    XYP = [tuple(map(int, input().split())) for i in range(N)]

    S = 0
    for x, y, p in XYP:
        S += min(abs(x), abs(y))*p

    print(S)

    dpX = [[0]*N for i in range(2**N)]

    dpY = [[0]*N for i in range(2**N)]

    for i in range(2**N):
        arr = []
        for j in range(N):
            if (i >> j) % 2 == 1:
                if (len(arr) == 0 or arr[-1] < 0) and XYP[j][0] > 0:
                    arr.append(0)
                arr.append(XYP[j][0])

        for j in range(N):
            if (i >> j) % 2 == 1:
                dpX[i][j] = 0
            else:
                X = XYP[j][0]
                id = bisect.bisect_left(arr, X)
                ret = abs(X)
                if id < len(arr):
                    ret = min(ret, arr[id] - X)
                if id > 0:
                    ret = min(ret, X - arr[id-1])
                dpX[i][j] = ret * XYP[j][2]

    for i in range(2**N):
        arr = []
        for j in range(N):
            if (i >> j) % 2 == 1:
                if (len(arr) == 0 or arr[-1] < 0) and XYP[j][1] > 0:
                    arr.append(0)
                arr.append(XYP[j][1])

        for j in range(N):
            if (i >> j) % 2 == 1:
                dpY[i][j] = 0
            else:
                Y = XYP[j][1]
                id = bisect.bisect_left(arr, Y)
                ret = abs(Y)
                if id < len(arr):
                    ret = min(ret, arr[id] - Y)
                if id > 0:
                    ret = min(ret, Y - arr[id-1])
                dpY[i][j] = ret * XYP[j][2]

    ans = [S]*N

    for i in range(1, N+1):
        for j in range(i+1):
            k = i - j
            for x in combinations(range(N), j):
                idx = 0
                for xx in x:
                    idx += 1 << xx
                dX = dpX[idx]
                for y in combinations(range(N), k):
                    tmp = 0
                    idy = 0
                    for yy in y:
                        idy += 1 << yy
                    if idx & idy > 0:
                        continue
                    dY = dpY[idy]
                    tmp = 0
                    for x, y in zip(dX, dY):
                        if x > y:
                            tmp += y
                        else:
                            tmp += x
                    if tmp < ans[i-1]:
                        ans[i-1] = tmp
    for i in range(N):
        print(ans[i])


main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
n = int(input())

x = []
y = []
p = []
for i in range(n):
    xx,yy,pp = map(int,input().split())
    x.append(xx+10000)
    y.append(yy+10000)
    p.append(pp)

yokomi = [[10**9]*(1<<n) for i in range(n)]
tatemi = [[10**9]*(1<<n) for i in range(n)]


for i in range(1<<n):
    yoko = [10000]
    tate = [10000]
    for j in range(n):
        if (i>>j)&1 == 1:
            yoko.append(y[j])
            tate.append(x[j])
    for j in range(n):
        pp = 10**9
        qq = 10**9
        for e in yoko:
            if pp > abs(e-y[j]):
                pp = abs(e-y[j])
        for e in tate:
            if qq > abs(e-x[j]):
                qq = min(qq,abs(e-x[j]))
        yokomi[j][i] = pp
        tatemi[j][i] = qq

def iter_p_adic(p, n):
    tmp = [range(p)] * n
    return product(*tmp)

res = [10**20]*(n+1)


iterator = iter_p_adic(3,n)
for idxs in iterator:
    yoko = set([10000])
    tate = set([10000])
    
    xn = 0
    yn = 0
    for i in range(n):
        if idxs[i] == 1:
            yoko.add(y[i])
            yn += 1<<i
        elif idxs[i] == 2:
            tate.add(x[i])
            xn += 1<<i

    tmp = 0
    for i in range(n):
        if idxs[i] == 0:
            mi = min(tatemi[i][xn],yokomi[i][yn])
            tmp += p[i]*mi

    residx = len(yoko) + len(tate) - 2
    if tmp == 0 and res[residx] != 0:
        for j in range(residx,n+1):
            res[j] = 0
    elif residx < n+1 and res[residx] > tmp:
        res[residx] = tmp
for e in res:
    print(e)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
X = []
Y = []
P = []
for i in range(N):
    x, y, p = map(int, input().split())
    X += [x]
    Y += [y]
    P += [p]
base_list = [i for i in range(N)]
base_cost = [min(abs(x), abs(y)) for x, y in zip(X, Y)]
flag = False
for k in range(0, N+1):
    if flag:
        print(0)
        continue
    ans = sum([d*p for d, p in zip(base_cost, P)])
    comb_gen = itertools.combinations(base_list, k)
    for comb in comb_gen:
        for b in range(2**k):
            cost = base_cost.copy()
            for ci in comb:
                if b & 1:
                    for i in range(N):
                        cost[i] = min(abs(Y[ci]-Y[i]), cost[i])
                else:
                    for i in range(N):
                        cost[i] = min(abs(X[ci]-X[i]), cost[i])
                b = b >> 1
            ans = min(ans, sum([d*p for d, p in zip(cost, P)]))
    print(ans)
    if ans == 0:
        flag = True

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools


def _cost(xs, ys, info):
    return int(sum(
        [p * min(min([math.fabs(x - xx) for xx in xs]), min([math.fabs(y - yy) for yy in ys])) for x, y, p in info]))


def _run(n, info):
    xs = [(True, x) for x, y, p in info]
    ys = [(False, y) for x, y, p in info]
    all = []
    all.extend(xs)
    all.extend(ys)

    d_cost = _cost([0], [0], info)
    print(d_cost)
    is_zero = False
    for i in range(n):
        if not is_zero:
            cost = d_cost
            for c in itertools.combinations(all, i + 1):
                xxs = [0]
                yys = [0]
                for is_x, v in c:
                    if is_x:
                        xxs.append(v)
                    else:
                        yys.append(v)
                cost = min(cost, _cost(xxs, yys, info))
                if cost == 0:
                    is_zero = True
                    break
            print(cost)
        else:
            print(0)


def _main():
    N = int(input())
    info = []
    for i in range(N):
        x, y, p = map(int, input().split())
        info.append((x, y, p))
    _run(N, info)


if __name__ == "__main__":
    _main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import bisect

n = int(input())
X, Y, P = [], [], []
for i in range(n):
    x, y, p = map(int, input().split())
    X.append(x), Y.append(y), P.append(p)

ans = [float('inf')] * (n+1)
for choice in product([0, 1, 2], repeat=n):
    NS = set()
    WE = set()
    for i, c in enumerate(choice):
        if c == 0:
            # 選ばない
            continue
        elif c == 1:
            # 南北に引く
            NS.add(Y[i])
        else:
            # 東西に引く
            WE.add(X[i])
    NS = list(NS)
    WE = list(WE)
    line = len(NS)+len(WE)
    temp = 0
    for i in range(n):
        vmin = abs(X[i] * P[i])
        for v in WE:
            vmin = min(vmin, abs(X[i]-v)*P[i])
        hmin = abs(Y[i] * P[i])
        for h in NS:
            hmin = min(hmin, abs(Y[i]-h)*P[i])
        temp += min(hmin, vmin)
    ans[line] = min(ans[line], temp)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import defaultdict

N = int(input())
Cities = [list(map(int, input().split())) for i in range(N)]
Distances = Cities.copy()
ans = defaultdict(lambda: float('inf'))
comb = tuple(itertools.product(range(3),repeat=N))
def calc(direction):
    x_list = direction['x']
    y_list = direction['y']
    ans = 0
    for c in Cities:
        x, y, p = c
        res = float('inf')
        for i in x_list:
            res = min(res, abs(x-i))
        for j in y_list:
            res = min(res, abs(y-j))
        ans += res*p
    return ans

kmax = N
for c in comb:
    direction = {'x':{0}, 'y':{0}}
    k = 0
    for i in range(N):
        x, y, p = Cities[i]
        if c[i]:
            k += 1
            if c[i] == 1:
                direction['x'].add(x)
            else:
                direction['y'].add(y)
    ans[k] = min(ans[k], calc(direction))

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
cities = []
for i in range(N):
    X,Y,P = map(int,input().split())
    cities.append([X,Y,P])
line = [float('inf')]*(N+1)
costs = []
for x,y,p in cities:
    costs.append(p*min(abs(x),abs(y)))
costssum = sum(costs)
def func(D,V,K):
    global costssum
    queue = []
    if V == 0:
        K -= 1
    if V == 1:
        X = cities[D][0]
        for i in range(N):
            ncost = abs(cities[i][0]-X)*cities[i][2]
            if costs[i] > ncost:
                queue.append((i,costs[i]))
                costssum-=costs[i]-ncost
                costs[i] = ncost
    if V == 2:
        Y = cities[D][1]
        for i in range(N):
            ncost = abs(cities[i][1]-Y)*cities[i][2]
            if costs[i] > ncost:
                queue.append((i,costs[i]))
                costssum-=costs[i]-ncost
                costs[i] = ncost
    if D == N-1:
        line[K] = min(line[K],costssum)
        for i,cost in queue:
            costssum += cost-costs[i]
            costs[i] = cost
        return
    for i in range(3):
        func(D+1,i,K)
    for i,cost in queue:
        costssum += cost-costs[i]
        costs[i] = cost

for i in range(3):
    func(0,i,N)
for i in line:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# Fast IO (only use in integer input)

# import os,io
# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

minCost = [-1] * (N+1)

totalCases = 3 ** N

for i in range(totalCases):
    railRoad = []
    tmp = i
    for j in range(N):
        railRoad.append(tmp % 3)
        tmp //= 3
    numNewRailroad = sum(map(lambda x: 1 if x != 0 else 0,railRoad))
    minDistance = [-1] * N
    for j in range(N):
        minDistance[j] = min(abs(Resident[j][0]),abs(Resident[j][1]))
        for k in range(N):
            if railRoad[k] == 1 and abs(Resident[j][0] - Resident[k][0]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][0] - Resident[k][0])
            if railRoad[k] == 2 and abs(Resident[j][1] - Resident[k][1]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][1] - Resident[k][1])
    cost = 0
    for j in range(N):
        cost += Resident[j][2] * minDistance[j]
    if minCost[numNewRailroad] == -1 or minCost[numNewRailroad] > cost:
        minCost[numNewRailroad] = cost
print('\n'.join(list(map(str,minCost))))

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

from itertools import combinations

def resolve():
    n = int(input())
    xyp = [list(map(int, input().split())) for _ in range(n)]

    # 全パターン、先に計算しておく
    # 探索空間
    xx = [x for x, _, _ in xyp]
    yy = [y for _, y, _ in xyp]
    inf = 10 ** 32

    xx_combinations = [[x_list for x_list in combinations(xx, i)] for i in range(0, n + 1)]
    yy_combinations = [[y_list for y_list in combinations(yy, i)] for i in range(0, n + 1)]

    # print(xx_combinations)
    # xx_min = dict()
    # for x_list in xx_combinations:
    #     for x, _, _ in xyp:
    #         xx_min[x_list] = \
    #             min([abs(x)] + [abs(x - x_line) for x_tmp in x_list for x_line in x_tmp])
    #
    # yy_min = dict()
    # for y_list in yy_combinations:
    #     for _, y, _ in xyp:
    #         yy_min[y_list] = min([abs(y)] + [abs(y - y_line) for y_line in y_list])

    print(sum([min(abs(x), abs(y)) * p for x, y, p in xyp]))

    for i in range(1, n + 1):
        tmp_ans = inf
        for j in range(i + 1):
            for x_list in xx_combinations[j]:
                for y_list in yy_combinations[i - j]:
                    tmp = sum([
                        min(
                            min([abs(x)] + [abs(x - x_line) for x_line in x_list]),
                            min([abs(y)] + [abs(y - y_line) for y_line in y_list])
                        ) * p for x, y, p in xyp
                    ])

                    if tmp < tmp_ans:
                        tmp_ans = tmp

        print(tmp_ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1 2 300
3 3 600
1 4 800"""
        output = """2900
900
0
0"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400"""
        output = """13800
1600
0
0
0
0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200"""
        output = """26700
13900
3200
1200
0
0
0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """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"""
        output = """2576709
1569381
868031
605676
366338
141903
0
0
0"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def score(CITIES, lines):
    s = 0
    for c in CITIES:
        x = c[0]
        y = c[1]
        p = c[2]

        min_dist = 1000000000000
        for l in lines:
            if l[1] == "H":
                dist = abs(y-l[0])
            else:
                dist = abs(x-l[0])
            min_dist = min(min_dist, dist)
        s += min_dist * p
    return s

def recursive_score(K, CITIES, candidate_lines, selected, max_selected):
    if len(selected) == K:
        lines = [[0, "H"], [0, "V"]]
        for s in selected:
            lines.append(candidate_lines[s])
        return score(CITIES, lines)

    min_score = 1000000000000
    for i in range(len(candidate_lines)):
        if i <= max_selected:
            continue
        max_selected = i
        sel = selected + [i]
        s = recursive_score(K, CITIES, candidate_lines, sel, max_selected)
        min_score = min(min_score, s)
    return min_score

def main():
    N = int(input())
    CITIES = []

    for i in range(N):
        # x=c[0]
        # y=c[1]
        # p=c[2]
        c = [int(_x) for _x in input().split()]
        CITIES.append(c)

    candidate_lines = []
    for i in range(N):
        candidate_lines.append([CITIES[i][1], "H"])  # y座標が同じで横線
        candidate_lines.append([CITIES[i][0], "V"])  # x座標が同じで縦線

    for K in range(N+1):
        S = recursive_score(K, CITIES, candidate_lines, [], -1)
        print(S)

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N = int(input())

XYP = []
x = set()
y = set()
for _ in range(N):
    X, Y, P = map(int, input().split())
    if X == 0 or Y == 0:
        continue
    x.add(X)
    y.add(Y)
    XYP.append((X, Y, P))

S = float('inf')
for K in range(N + 1):
    if S != 0:
        S = float('inf')
        for k in range(min(len(x) + 1, K + 1)):
            for cx in combinations(x, k):
                xx = [0] + list(cx)
                for cy in combinations(y, K - k):
                    yy = [0] + list(cy)
                    t = 0
                    for X, Y, P in XYP:
                        m = min(min(abs(X - i) for i in xx), min(abs(Y - i) for i in yy))
                        t += m * P
                        if t >= S:
                            break
                    S = min(S, t)
                    if S == 0:
                        break
                if S == 0:
                    break
            if S == 0:
                break
        print(S)
    else:
        print(0)

Submission status: Time Limit Exceeded

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

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

for rail in range(N-1):
    I=combinations(range(N),rail)

    for rails in I:
        #print(rails)
        if ANS==0:
            break

        for i in range(1<<rail):
            X=[0]
            Y=[0]
            for j in range(rail):
                if (1<<j) & i ==0:
                    X.append(P[rails[j]][0])
                else:
                    Y.append(P[rails[j]][1])

            C=0
            for x,y,p in P:
                MIN=1<<30
                for xx in X:
                    MIN=min(abs(xx-x),MIN)
                for yy in Y:
                    MIN=min(abs(yy-y),MIN)

                C+=MIN*p
                if C>=ANS:
                    break

            #print(X,Y,C)

            ANS=min(ANS,C)

    print(ANS)

ANS=1<<60
for x,y,c in P:
    ANS=min(ANS,abs(x)*c,abs(y)*c)
    for xx,yy,cc in P:
        if x==xx and y==yy:
            continue
        ANS=min(ANS,abs(x-xx)*c,abs(y-yy)*c)

print(ANS)
print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
towns = []  # coordinates, populations of towns

for _ in range(n):
    x, y, p = map(int, input().split())
    towns.append((x, y, p))

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

for bit in range(1 << n):
    k = bin(bit).count('1')
    i = 0
    t = bit
    selected = []
    while t:
        if t & 1:
            selected.append(i)
        t >>= 1
        i += 1

    for bit2 in range(1 << k):
        i = 0
        t = bit2
        road = [set(), set()]
        for _ in range(k):
            road[t & 1].add(towns[selected[i]][t & 1])
            t >>= 1
            i += 1
        cost = 0
        for x, y, p in towns:
            town_dist = min(abs(x), abs(y))
            for rx in road[0]:
                town_dist = min(town_dist, abs(rx - x))
            for ry in road[1]:
                town_dist = min(town_dist, abs(ry - y))
            cost += town_dist * p
        kk = len(selected)
        ans[kk] = min(ans[kk], cost)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13


costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))


x_dir = [[INF] * n for i in range(1 << n)]
y_dir = [[INF] * n for i in range(1 << n)]

for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[bit_state][i] = min(costs[i], x_dir[bit_state][i])
        y_dir[bit_state][i] = min(costs[i], y_dir[bit_state][i])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[bit_state][j] = min(x_dir[bit_state][j], c * abs(yi - yj))
            y_dir[bit_state][j] = min(y_dir[bit_state][j], c * abs(xi - xj))


ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[x_bit][i], y_dir[y_bit][i])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

ans[-1] = 0
for res in ans:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools


def _cost(xs, ys, info):
    return int(sum(
        [p * min(min([math.fabs(x - xx) for xx in xs]), min([math.fabs(y - yy) for yy in ys])) for x, y, p in info]))


def _run(n, info):
    xs = [(True, x) for x, y, p in info]
    ys = [(False, y) for x, y, p in info]
    all = []
    all.extend(xs)
    all.extend(ys)

    d_cost =_cost([0], [0], info)
    print(d_cost)
    for i in range(n):
        cost = d_cost
        for c in itertools.combinations(all, i + 1):
            xxs = [0]
            yys = [0]
            for is_x ,v in c:
                if is_x:
                    xxs.append(v)
                else:
                    yys.append(v)
            cost = min(cost,_cost(xxs, yys, info))
        print(cost)


def _main():
    N = int(input())
    info = []
    for i in range(N):
        x, y, p = map(int, input().split())
        info.append((x, y, p))
    _run(N, info)


if __name__ == "__main__":
    _main()

Submission status: Time Limit Exceeded

Solution code:

def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


def main():
    from itertools import combinations
    import bisect
    N = int(input())
    XYP = [tuple(map(int, input().split())) for i in range(N)]

    S = 0
    for x, y, p in XYP:
        S += min(abs(x), abs(y))*p

    print(S)

    dpX = [[0]*N for i in range(2**N)]

    dpY = [[0]*N for i in range(2**N)]

    for i in range(2**N):
        arr = []
        for j in range(N):
            if (i >> j) % 2 == 1:
                if (len(arr) == 0 or arr[-1] < 0) and XYP[j][0] > 0:
                    arr.append(0)
                arr.append(XYP[j][0])

        for j in range(N):
            if (i >> j) % 2 == 1:
                dpX[i][j] = 0
            else:
                X = XYP[j][0]
                id = bisect.bisect_left(arr, X)
                ret = abs(X)
                if id < len(arr):
                    ret = min(ret, arr[id] - X)
                if id > 0:
                    ret = min(ret, X - arr[id-1])
                dpX[i][j] = ret * XYP[j][2]

    for i in range(2**N):
        arr = []
        for j in range(N):
            if (i >> j) % 2 == 1:
                if (len(arr) == 0 or arr[-1] < 0) and XYP[j][1] > 0:
                    arr.append(0)
                arr.append(XYP[j][1])

        for j in range(N):
            if (i >> j) % 2 == 1:
                dpY[i][j] = 0
            else:
                Y = XYP[j][1]
                id = bisect.bisect_left(arr, Y)
                ret = abs(Y)
                if id < len(arr):
                    ret = min(ret, arr[id] - Y)
                if id > 0:
                    ret = min(ret, Y - arr[id-1])
                dpY[i][j] = ret * XYP[j][2]

    ans = [S]*N

    for i in range(1, N+1):
        for j in range(i+1):
            k = i - j
            for x in combinations(range(N), j):
                idx = 0
                for xx in x:
                    idx += 1 << xx
                dX = dpX[idx]
                for y in combinations(range(N), k):
                    tmp = 0
                    idy = 0
                    for yy in y:
                        idy += 1 << yy

                    dY = dpY[idy]
                    tmp = 0
                    for x, y in zip(dX, dY):
                        if x > y:
                            tmp += y
                        else:
                            tmp += x
                    if tmp < ans[i-1]:
                        ans[i-1] = tmp

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


main()