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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
sys.setrecursionlimit(10**6)
INF = 10 ** 11  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, data):
    xs, ys, ps = data.reshape((N, 3)).T

    candidate = [(0, x) for x in xs]
    candidate += [(1, y) for y in ys]
    candidate = list(sorted(set(candidate)))

    NUM_LINES = len(candidate)
    dist = np.minimum(np.abs(xs), np.abs(ys))
    # debug(": dist", dist)

    start = 0
    distmemo = [None] * ((1 << NUM_LINES) + 10)
    scorememo = [INF] * (N + 1)
    distmemo[start] = dist
    scorememo[start] = (dist * ps).sum()
    # debug(": (dist * ps).sum()", (dist * ps).sum())

    def f(cursor, parent, numbits):
        if cursor == N:
            return

        # add no lines
        f(cursor + 1, parent, numbits)

        # add vertical (x) line
        x = xs[cursor]
        lineid = candidate.index((0, x))
        new_parent = parent | (1 << lineid)
        if parent != new_parent:
            parent_dist = distmemo[parent]
            dist = np.minimum(parent_dist, np.abs(xs - x))
            distmemo[new_parent] = dist
            # debug(": ", f"{new_parent:05b}", dist)
            score = (dist * ps).sum()
            n = numbits + 1
            scorememo[n] = min(scorememo[n], score)
            f(cursor + 1, new_parent, n)

        # add vertical (x) line
        y = ys[cursor]
        lineid = candidate.index((1, y))
        new_parent = parent | (1 << lineid)
        if parent != new_parent:
            parent_dist = distmemo[parent]
            dist = np.minimum(parent_dist, np.abs(ys - y))
            distmemo[new_parent] = dist
            # debug(": ", f"{new_parent:05b}", dist)
            score = (dist * ps).sum()
            n = numbits + 1
            scorememo[n] = min(scorememo[n], score)
            f(cursor + 1, new_parent, n)

    f(0, start, 0)
    # debug(": scorememo", scorememo)
    return scorememo


def main():
    # parse input
    N = int(input())
    data = np.int64(read().split())
    print(*solve(N, data), sep="\n")


# tests
T1 = """
3
1 2 300
3 3 600
1 4 800
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
2900
900
0
0
"""

T2 = """
5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
13800
1600
0
0
0
0
"""

T3 = """
6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
26700
13900
3200
1200
0
0
0
"""

T4 = """
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
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2576709
1569381
868031
605676
366338
141903
0
0
0
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
sys.setrecursionlimit(10**6)
INF = 10 ** 11  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, data):
    xs, ys, ps = data.reshape((N, 3)).T

    candidate = [(0, x) for x in xs]
    candidate += [(1, y) for y in ys]
    candidate = list(sorted(set(candidate)))

    NUM_LINES = len(candidate)
    dist = np.minimum(np.abs(xs), np.abs(ys))
    # debug(": dist", dist)

    start = 0
    distmemo = [None] * (1 << NUM_LINES + 1)
    scorememo = [INF] * (N + 1)
    distmemo[start] = dist
    scorememo[start] = (dist * ps).sum()
    # debug(": (dist * ps).sum()", (dist * ps).sum())

    def f(cursor, parent, numbits):
        if cursor == NUM_LINES:
            return
        if numbits == N:
            return

        f(cursor + 1, parent, numbits)

        new_parent = parent | (1 << cursor)
        numbits += 1
        isY, line = candidate[cursor]
        parent_dist = distmemo[parent]
        if isY:
            dist = np.minimum(parent_dist, np.abs(ys - line))
        else:
            dist = np.minimum(parent_dist, np.abs(xs - line))
        distmemo[new_parent] = dist
        # debug(": ", f"{new_parent:05b}", dist)
        score = (dist * ps).sum()
        scorememo[numbits] = min(scorememo[numbits], score)
        f(cursor + 1, new_parent, numbits)

    f(0, 0, 0)
    # debug(": scorememo", scorememo)
    return scorememo


def main():
    # parse input
    N = int(input())
    data = np.int64(read().split())
    print(*solve(N, data), sep="\n")


# tests
T1 = """
3
1 2 300
3 3 600
1 4 800
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
2900
900
0
0
"""

T2 = """
5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
13800
1600
0
0
0
0
"""

T3 = """
6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
26700
13900
3200
1200
0
0
0
"""

T4 = """
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
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2576709
1569381
868031
605676
366338
141903
0
0
0
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
sys.setrecursionlimit(10**6)
INF = 10 ** 11  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, data):
    xs, ys, ps = data.reshape((N, 3)).T

    candidate = [(0, x) for x in xs]
    candidate += [(1, y) for y in ys]
    candidate = list(sorted(set(candidate)))

    NUM_LINES = len(candidate)
    dist = np.minimum(np.abs(xs), np.abs(ys))
    # debug(": dist", dist)

    start = 0
    distmemo = [None] * (1 << NUM_LINES)
    scorememo = [INF] * (N + 1)
    distmemo[start] = dist
    scorememo[start] = (dist * ps).sum()
    # debug(": (dist * ps).sum()", (dist * ps).sum())

    def f(cursor, parent, numbits):
        if cursor == NUM_LINES:
            return
        if numbits == N:
            return

        f(cursor + 1, parent, numbits)

        new_parent = parent | (1 << cursor)
        numbits += 1
        isY, line = candidate[cursor]
        parent_dist = distmemo[parent]
        if isY:
            dist = np.minimum(parent_dist, np.abs(ys - line))
        else:
            dist = np.minimum(parent_dist, np.abs(xs - line))
        distmemo[new_parent] = dist
        # debug(": ", f"{new_parent:05b}", dist)
        score = (dist * ps).sum()
        scorememo[numbits] = min(scorememo[numbits], score)
        f(cursor + 1, new_parent, numbits)

    f(0, 0, 0)
    # debug(": scorememo", scorememo)
    return scorememo


def main():
    # parse input
    N = int(input())
    data = np.int64(read().split())
    print(*solve(N, data), sep="\n")


# tests
T1 = """
3
1 2 300
3 3 600
1 4 800
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
2900
900
0
0
"""

T2 = """
5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
13800
1600
0
0
0
0
"""

T3 = """
6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
26700
13900
3200
1200
0
0
0
"""

T4 = """
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
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2576709
1569381
868031
605676
366338
141903
0
0
0
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
import numpy as np
#from copy import deepcopy
#from collections import deque


def run():
    N = int(sysread())
    INF = 1 << 50
    X, Y, P = [], [], []
    ans = [INF] * N

    INF = 1 << 50

    dist_arr = np.zeros([2 * (N+1), N+1], dtype= np.int64)
    for i in range(1, N+1):
        x,y,p = map(int, sysread().split())
        X.append(x)
        Y.append(y)
        P.append(p)
        dist_arr[0, i] = abs(x) * p
        dist_arr[N+1, i] = abs(y) * p

    ans = [INF] * (N + 1)

    for i in range(1 << N):# x-y-directions
        dist_towns_x = [INF] * (N + 1)
        dist_towns_y = [INF] * (N + 1)
        x_town_list = []
        y_town_list = []
        for k in range(N):
            if i >> k & 1:
                x_town_list.append(k)
            else:
                y_town_list.append(k)


        for j in range(1 << N):  # x-lines
            x_lines_list = [0]

            for k in range(N):
                if j >> k & 1:
                    x_lines_list.append(Y[k])

            dist_ = [INF] * len(x_town_list)
            for line in x_lines_list:
                for idx, k in enumerate(x_town_list):
                    dist_[idx] = min(abs(line - X[k])*P[k], dist_[idx])
            tmp = len(x_lines_list)-1
            dist_towns_x[tmp] = min(sum(dist_), dist_towns_x[tmp])


        for j in range(1 << N):  # y-lines
            y_lines_list = [0]

            for k in range(N):
                if j >> k & 1:
                    y_lines_list.append(Y[k])

            dist_ = [INF] * len(y_town_list)
            for line in y_lines_list:
                for idx, k in enumerate(y_town_list):
                    dist_[idx] = min(abs(line - Y[k])*P[k], dist_[idx])
            tmp = len(y_lines_list)-1
                #print(y_lines_list)
            dist_towns_y[tmp] = min(sum(dist_), dist_towns_y[tmp])

        #print(bin(i))
        #print(dist_towns_x)
        #print(dist_towns_y)

        for i in range(N + 1):
            for j in range(N + 1 - i):
                val = dist_towns_x[i] + dist_towns_y[j]
                ans[i + j] = min(ans[i + j], val)


    for a in ans:
        print(a)


if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
import itertools

n = int(input())
people = []
for _ in range(n):
  x, y, p = map(int, input().split())
  people.append((x, y, p))
people_sorted = sorted(people, key=lambda x: -x[2])

points = []
for i in range(n+1):
  if i == 0:
    total = 0
    for x, y, p in people_sorted:
      total += p * min(x, y)
    print(total)
  else:
    x, y, p = people_sorted[i-1]
    points.append((x, 0))
    points.append((0, y))
    all_total = 10**20
    for v in itertools.permutations(people_sorted, i):
      total = 0
      for j in range(i, n):
        x, y, p = people_sorted[j]
        dist = p * min(x, y)
        for a, b in v:
          if a == 0:
            k = p * abs(y-b)
          else:
            k = p * abs(x-a)
          if dist > k:
            dist = k
        total += dist
      if all_total > total:
        all_total = total
    print(all_total)

Submission status: Runtime Error

Solution code:
import itertools

n = int(input())
people = []
for _ in range(n):
  x, y, p = map(int, input().split())
  people.append((x, y, p))
people_sorted = sorted(people, key=lambda x: -x[2])

points = []
now_points = [(0, 0)]
for i in range(n+1):
  if i == 0:
    total = 0
    for x, y, p in people_sorted:
      total += p * min(x, y)
    print(total)
  else:
    x, y, p = people_sorted[i-1]
    points.append((x, 0))
    points.append((0, y))
    total = 0
    for j in range(i, n):
      x, y, p = people_sorted[j]
      dist = p * min(x, y)
      for v in itertools.permutation(points, i):
        for a, b in v:
          if dist > p * min(abs(x-a), abs(y-b)):
            dist = p * min(abs(x-a), abs(y-b))
      total += dist
    print(total)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
import numpy as np
#from copy import deepcopy
#from collections import deque


def run():
    N = int(sysread())
    INF = 1 << 50
    X, Y, P = [-1], [-1], [-1]
    ans = [INF] * (N+1)

    INF = 1 << 50
    hline = [0]
    vline = [0]
    dist_arr = np.zeros([2 * (N+1), N+1], dtype= np.int64)
    for i in range(1, N+1):
        x,y,p = map(int, sysread().split())
        X.append(x)
        Y.append(y)
        P.append(p)
        dist_arr[0, i] = abs(x) * p
        dist_arr[N+1, i] = abs(y) * p



    for i in range(1, N+1):
        v = X[i]
        h = Y[i]
        for k in range(1, N+1):
            # vertical
            dist_arr[i, k] = abs(v-X[k]) * P[k]
            dist_arr[N+1+i, k] = abs(h-Y[k]) * P[k]
    dist_arr = dist_arr[:, 1:]
    #print(dist_arr)

    for vals in product((0,1,2), repeat = N):
        xlines = set()
        ylines = set()
        idx = [0, N+1]
        for i, val in enumerate(vals, 1):
            if val == 0:
                continue
            elif val == 1:
                # vertical
                xlines.add(X[i])
                idx.append(i)
            else:
                ylines.add(Y[i])
                idx.append(N+1+i)
        k = len(xlines) + len(ylines)
        idx = np.array(idx)
        print(idx)
        #D = dist_arr[idx, :].min(axis = 0).sum()

        ans[k] = min(ans[k], D)

    for a in ans:
        print(a)


if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit, int64
import sys

read = sys.stdin.buffer.read


@njit((int64, int64[:], int64[:], ), cache=True)
def pre_calc(n, pos, coef):
    ret = np.empty((1 << n, n), np.int64)
    ret[0] = np.abs(pos) * coef

    for i in range(n):
        bt = 1 << i
        ret[bt:2 * bt] = np.minimum(ret[:bt], np.abs(pos - pos[i]) * coef)

    return ret


@njit((int64[:], ), cache=True)
def solve(inp):
    INF = 10 ** 18

    n = inp[0]
    x = inp[1::3]
    y = inp[2::3]
    p = inp[3::3]

    ver = pre_calc(n, x, p)
    hor = pre_calc(n, y, p)

    states = np.zeros((2, pow(3, n)), np.int16)
    cnts = np.zeros(pow(3, n), np.int8)
    for i in range(pow(3, n)):
        pw2 = 1
        now = i
        for j in range(n):
            r = now % 3
            if r != 0:
                states[r - 1, i] += pw2
                cnts[i] += 1
            pw2 *= 2
            now //= 3

    vals = np.minimum(ver[states[0]], hor[states[1]]).sum(axis=1)
    ans = [INF] * (n + 1)
    for ev, ec in zip(vals, cnts):
        ans[ec] = min(ans[ec], ev)

    return ans


inp = np.array(read().split(), np.int64)
ans = solve(inp)
print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit, int64
import sys

read = sys.stdin.buffer.read


@njit((int64, int64[:], int64[:], ), cache=True)
def pre_calc(n, pos, coef):
    ret = np.empty((1 << n, n), np.int64)
    ret[0] = np.abs(pos) * coef

    for i in range(n):
        bt = 1 << i
        ret[bt:2 * bt] = np.minimum(ret[:bt], np.abs(pos - pos[i]) * coef)

    return ret


@njit((int64[:], ), cache=True)
def solve(inp):
    INF = 10 ** 18

    n = inp[0]
    x = inp[1::3]
    y = inp[2::3]
    p = inp[3::3]

    ver = pre_calc(n, x, p)
    hor = pre_calc(n, y, p)

    states = np.zeros((2, pow(3, n)), np.int64)
    cnts = np.zeros(pow(3, n), np.int64)
    for i in range(pow(3, n)):
        pw2 = 1
        now = i
        for j in range(n):
            r = now % 3
            if r != 0:
                states[r - 1, i] += pw2
                cnts[i] += 1
            pw2 *= 2
            now //= 3

    vi, hi = states[0], states[1]
    vals = np.minimum(ver[vi], hor[hi]).sum(axis=1)
    ans = [INF] * (n + 1)
    for ev, ec in zip(vals, cnts):
        ans[ec] = min(ans[ec], ev)

    return ans


inp = np.array(read().split(), np.int64)
ans = solve(inp)
print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
from itertools import product
INF = 10**18

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: max(abs(xyp[0], xyp[1])) * xyp[2], reverse=True)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

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

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

sol()

Submission status: Runtime Error

Solution code:
from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

def makeState(state, sign):
    ret = 0
    for s in state:
        ret <<= 1
        if s == sign:
            ret |= 1
    return ret

ans = [INF] * (N + 1)
for state in product((0, 1, 2), repeat=N):
    stateX = 0
    stateY = 0
    M = N
    for s in state:
        stateX <<= 1
        stateY <<= 1
        if s == 0: N -= 1
        if s == 1: stateX |= 1
        if s == 2: stateY |= 1

    cx = costX[stateX]
    cy = costY[stateY]

    cost = sum(min(x, y) for x, y in zip(cx, cy))

    if ans[M] > cost:
        ans[M] = cost

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

Submission status: Runtime Error

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n = int(ipt())
    xs = []
    ys = []
    ps = []
    for i in range(n):
        x,y,p = map(int,ipt().split())
        xs.append(x)
        ys.append(y)
        ps.append(p)
    mix = [abs(i) for i in xs]
    miy = [abs(i) for i in ys]
    mi2x = []
    mi2y = []
    for i in range(2**n):
        mi = mix*1
        for j,xj in enumerate(xs):
            if (i>>j)&1:
                for k,xk in enumerate(xs):
                    ax = abs(xj-xk)
                    if mi[k] > ax:
                        mi[k] = ax
        mi = [mi[i]*ps[i] for i in range(n)]
        mi2x.append(mi)
    for i in range(2**n):
        mi = miy*1
        for j,yj in enumerate(ys):
            if (i>>j)&1:
                for k,yk in enumerate(ys):
                    ay = abs(yj-yk)
                    if mi[k] > ay:
                        mi[k] = ay
        mi = [mi[i]*ps[i] for i in range(n)]
        mi2y.append(mi)
'''
    mi = [10**18]*(n+1)
    for i in range(3**n):
        xi = 0
        yi = 0
        ii = i
        t = n
        for j in range(n):
            if ii%3 == 1:
                xi += 2**j
            elif ii%3 == 2:
                yi += 2**j
            else:
                t -= 1
            ii //= 3
        nm = 0
        for xii,yii in zip(mi2x[xi],mi2y[yi]):
            if xii > yii:
                nm += yii
            else:
                nm += xii
        if mi[t] > nm:
            mi[t] = nm

    for i in mi:
        print(i)
'''
    return None

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
l=[tuple(map(int,input().split()))for i in range(n)]
X,Y,P=zip(*l)
xs,ys,un=[],[],[]
res=[float('inf')]*(n+1)
for i in range(3**n):
    xs.clear()
    ys.clear()
    un.clear()
    for k in range(n):
        if i%3==0:xs.append(k)
        elif i%3==1:ys.append(k)
        else:un.append(k)
        i//=3
    preans=0

    for u in un:
        udist=min(abs((x:=X[u])),abs((y:=Y[u])))
        for xline in xs:
            udist=min(udist,abs(x-X[xline]))
        for yline in ys:
            udist=min(udist,abs(y-Y[yline]))
        preans+=P[u]*udist

    res[len(xs)+len(ys)]=min(res[len(xs)+len(ys)],preans)
for i in range(n+1):print(res[i])

Submission status: Runtime Error

Solution code:
#解法１

#入力
N = int(input())
town = [list(map(int,input().split())) for i in range(N)]

#縦と横のリストを作る
vert = [town[i][0] for i in range(N)]
hori = [town[i][1] for i in range(N)]

#bit全探索
dX = []
for i in range(2**N):
    vertsel = []
    dXconst = [abs(town[l][0])*town[l][2] for l in range(N)]
    for j in range(N):
        if ((i >> j) & 1):
            vertsel.append(town[j][0])
    for k in vertsel:
        dXconst = [min(dXconst[l],abs(town[l][0]-k)*town[l][2]) for l in range(N)]
    dX.append(dXconst)

dY = []
for i in range(2**N):
    horisel = []
    dYconst = [abs(town[l][1])*town[l][2] for l in range(N)]
    for j in range(N):
        if ((i >> j) & 1):
            horisel.append(town[j][1])
    for k in horisel:
        dYconst = [min(dYconst[l],abs(town[l][1]-k)*town[l][2]) for l in range(N)]
    dY.append(dYconst)

#print('len(dX) ==',len(dX))
#print('len(dY) ==',len(dY))
#print(dX)
#print(dY)

#歩行距離を3進数を使って求める
ans = [float('inf') for K in range(N+1)]
for i in range(2**N):
    #print(i)
    K = 0
    #print('i ==',i)
    for j in range(N):
        if ((i >> j) & 1):
            K += 1
    for j in reversed(range(i+1)):
        j = (j&i)
        cost = 0
        for k in range(N):
            if not ((i >> k) & 1):
                cost += min(dX[j][l], xY[i-j][l])
        ans[K] = min(cost,ans[K])

#出力
[print(ans[K]) for K in range(N+1)]

Submission status: Runtime Error

Solution code:
#解法１

#入力
N = int(input())
town = [list(map(int,input().split())) for i in range(N)]

#縦と横のリストを作る
vert = [town[i][0] for i in range(N)]
hori = [town[i][1] for i in range(N)]

#bit全探索
dX = []
for i in range(2**N):
    vertsel = []
    dXconst = [abs(town[l][0])*town[l][2] for l in range(N)]
    for j in range(N):
        if ((i >> j) & 1):
            vertsel.append(town[j][0])
    for k in vertsel:
        dXconst = [min(dXconst[l],abs(town[l][0]-k)*town[l][2]) for l in range(N)]
    dX.append(dXconst)

dY = []
for i in range(2**N):
    horisel = []
    dYconst = [abs(town[l][1])*town[l][2] for l in range(N)]
    for j in range(N):
        if ((i >> j) & 1):
            horisel.append(town[j][1])
    for k in horisel:
        dYconst = [min(dYconst[l],abs(town[l][1]-k)*town[l][2]) for l in range(N)]
    dY.append(dYconst)

#print('len(dX) ==',len(dX))
#print('len(dY) ==',len(dY))
#print(dX)
#print(dY)

#歩行距離を3進数を使って求める
ans = [float('inf') for K in range(N+1)]
for i in range(2**N):
    #print(i)
    Xvalue = 0
    Yvalue = 0
    K = 0
    #print('i ==',i)
    for j in range(N):
        if ((i >> j) & 1):
            K += 1
    for j in reversed(range(i+1)):
        j = (j&i)
        cost = 0
        for k in range(N):
            if not ((i >> k) & 1):
                cost += min(dX[j][k], dYsel[i-j][k])*town[k][2]
    ans[K] = min(sum([min(dX[Xvalue][l],dY[Yvalue][l]) for l in range(N)]),ans[K])

#出力
[print(ans[K]) for K in range(N+1)]

Submission status: Runtime Error

Solution code:
#解法１

#入力
N = int(input())
town = [list(map(int,input().split())) for i in range(N)]

#縦と横のリストを作る
vert = [town[i][0] for i in range(N)]
hori = [town[i][1] for i in range(N)]

#bit全探索
dX = []
for i in range(2**N):
    vertsel = []
    dXconst = [abs(town[l][0])*town[l][2] for l in range(N)]
    for j in range(N):
        if ((i >> j) & 1):
            vertsel.append(town[j][0])
    for k in vertsel:
        dXconst = [min(dXconst[l],abs(town[l][0]-k)*town[l][2]) for l in range(N)]
    dX.append(dXconst)

dY = []
for i in range(2**N):
    horisel = []
    dYconst = [abs(town[l][1])*town[l][2] for l in range(N)]
    for j in range(N):
        if ((i >> j) & 1):
            horisel.append(town[j][1])
    for k in horisel:
        dYconst = [min(dYconst[l],abs(town[l][1]-k)*town[l][2]) for l in range(N)]
    dY.append(dYconst)

#print('len(dX) ==',len(dX))
#print('len(dY) ==',len(dY))
#print(dX)
#print(dY)

#歩行距離を3進数を使って求める
ans = [float('inf') for K in range(N+1)]
for i in range(2**N):
    #print(i)
    Xvalue = 0
    Yvalue = 0
    K = 0
    #print('i ==',i)
    for j in range(N):
        if ((i >> j) & 1):
            K += 1
    for j in reversed(range(i+1)):
        j = (j&i)
        cost = 0
        for k in range(N):
            if not ((i >> k) & 1):
                cost += min(dX[j][k], DYsel[i-j][k])*town[k][2]
    ans[K] = min(sum([min(dX[Xvalue][l],dY[Yvalue][l]) for l in range(N)]),ans[K])

#出力
[print(ans[K]) for K in range(N+1)]