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:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics.Contracts;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Xml.Schema;
using System.Threading;
using System.Diagnostics.CodeAnalysis;
using System.Security.Cryptography;
using System.IO.Pipes;
using Microsoft.Win32;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.CodeDom;
using System.Diagnostics.SymbolStore;

namespace AtCoder
{
    public static class Ex
    {
        public static List<string> FastSort(this List<string> s) { s.Sort(StringComparer.OrdinalIgnoreCase); return s.ToList(); }
        public static void yesno(this bool b) { Console.WriteLine(b ? "yes" : "no"); }
        public static void YesNo(this bool b) { Console.WriteLine(b ? "Yes" : "No"); }
        public static void YESNO(this bool b) { Console.WriteLine(b ? "YES" : "NO"); }

        public static int PopCount(this int bits)
        {
            bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
            bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
            bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
            bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
            return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
        }
    }

    partial class AtCoder
    {
        public string GetStr() { return Console.ReadLine().Trim(); }
        public char GetChar() { return Console.ReadLine().Trim()[0]; }
        public int GetInt() { return int.Parse(Console.ReadLine().Trim()); }
        public long GetLong() { return long.Parse(Console.ReadLine().Trim()); }
        public double GetDouble() { return double.Parse(Console.ReadLine().Trim()); }
        public string[] GetStrArray() { return Console.ReadLine().Trim().Split(' '); }
        public int[] GetIntArray() { return Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray(); }
        public long[] GetLongArray() { return Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray(); }
        public char[] GetCharArray() { return Console.ReadLine().Trim().Split(' ').Select(char.Parse).ToArray(); }
        public double[] GetDoubleArray() { return Console.ReadLine().Trim().Split(' ').Select(double.Parse).ToArray(); }
        public T[][] CreateJaggedArray<T>(int H, int W, T value) { return Enumerable.Repeat(0, H).Select(s => Enumerable.Repeat(value, W).ToArray()).ToArray(); }
        public int[][] GetIntJaggedArray(int N) { return Enumerable.Repeat(0, N).Select(s => GetIntArray().ToArray()).ToArray(); }
        public long[][] GetLongJaggedArray(int N) { return Enumerable.Repeat(0, N).Select(s => GetLongArray().ToArray()).ToArray(); }
        public char[][] GetCharJaggedArray(int N) { return Enumerable.Repeat(0, N).Select(s => GetStr().ToCharArray()).ToArray(); }
        public double[][] GetDoubleJaggedArray(int N) { return Enumerable.Repeat(0, N).Select(s => GetDoubleArray()).ToArray(); }

        Dictionary<int, List<int>> GetUnweightedAdjacencyList(int N, int M, bool isDirected, bool isNode_0indexed)
        {
            var dic = new Dictionary<int, List<int>>();
            foreach (var e in Enumerable.Range(0, N)) { dic.Add(e, new List<int>()); }
            for (int i = 0; i < M; i++)
            {
                var input = GetIntArray();
                var a = isNode_0indexed ? input[0] : input[0] - 1;
                var b = isNode_0indexed ? input[1] : input[1] - 1;
                dic[a].Add(b);
                if (isDirected == false) dic[b].Add(a);
            }
            return dic;
        }
        Dictionary<int, List<Edge>> GetWeightedAdjacencyList(int N, int M, bool isDirected, bool isNode_0indexed)
        {
            var dic = new Dictionary<int, List<Edge>>();
            foreach (var e in Enumerable.Range(0, N)) { dic.Add(e, new List<Edge>()); }
            for (int i = 0; i < M; i++)
            {
                var input = GetIntArray();
                var a = isNode_0indexed ? input[0] : input[0] - 1;
                var b = isNode_0indexed ? input[1] : input[1] - 1;
                var c = input[2];
                dic[a].Add(new Edge(b, c));
                if (isDirected == false) dic[b].Add(new Edge(a, c));
            }
            return dic;
        }

        bool eq<T, U>() => typeof(T).Equals(typeof(U));
        T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
        T cv<T>(string s) => eq<T, int>() ? ct<T, int>(int.Parse(s))
                           : eq<T, long>() ? ct<T, long>(long.Parse(s))
                           : eq<T, double>() ? ct<T, double>(double.Parse(s))
                           : eq<T, char>() ? ct<T, char>(s[0])
                                             : ct<T, string>(s);
        void Multi<T>(out T a) => a = cv<T>(GetStr());
        void Multi<T, U>(out T a, out U b)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]);
        }
        void Multi<T, U, V>(out T a, out U b, out V c)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]);
        }
        void Multi<T, U, V, W>(out T a, out U b, out V c, out W d)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]);
        }
        void Multi<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); e = cv<X>(ar[4]);
        }
        void Multi<T, U, V, W, X, Y>(out T a, out U b, out V c, out W d, out X e, out Y f)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); e = cv<X>(ar[4]); f = cv<Y>(ar[5]);
        }
    }

    class Edge
    {
        public Edge(int to, long length)
        {
            To = to;
            Length = length;
        }
        public int To { get; set; }
        public long Length { get; set; }
    }

    class Comparable : IComparable<Comparable>
    {
        public Comparable(int value)
        {
            this.value = value;
        }

        public int value;
        public int CompareTo(Comparable c)
        {
            return this.value < c.value ? 1 : this.value == c.value ? 0 : -1;
        }
    }



    partial class Program
    {
        static void Main()
        {
            Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
            new AtCoder().Solve();
            Console.Out.Flush();
            Console.Read();
        }
    }

    public partial class AtCoder
    {
        public void Solve()
        {
            int N = GetInt();
            var map = GetLongJaggedArray(N).Select(s => new { x = s[0], y = s[1], p = s[2] }).ToArray();
            var xmin = CreateJaggedArray(1 << N, N, 0L);
            var ymin = CreateJaggedArray(1 << N, N, 0L);
            var min = Enumerable.Repeat(long.MaxValue, N + 1).ToArray();

            List<long> xls;
            List<long> yls;
            for (int bit = 0; bit < 1 << N; bit++)
            {
                xls = new List<long>();
                xls.Add(0);
                for (int i = 0; i < N; i++) if (((bit >> i) & 1) == 1) xls.Add(map[i].x);
                for (int i = 0; i < N; i++) xmin[bit][i] = xls.Min(m => Math.Abs(m - map[i].x));
            }
            for (int bit = 0; bit < 1 << N; bit++)
            {
                yls = new List<long>();
                yls.Add(0);
                for (int i = 0; i < N; i++) if (((bit >> i) & 1) == 1) yls.Add(map[i].y);
                for (int i = 0; i < N; i++) ymin[bit][i] = yls.Min(m => Math.Abs(m - map[i].y));
            }

            for (int trit = 0; trit < (int)Math.Pow(3, N); trit++)
            {
                var tmp = trit;
                var xbit = 0;
                var ybit = 0;
                var cnt = N;
                for (int i = 0; i < N; i++)
                {
                    var t = tmp % 3;
                    tmp /= 3;
                    if (t == 0) cnt--;
                    if (t == 1) xbit += 1 << i;
                    if (t == 2) ybit += 1 << i;
                }
                long sum = 0;
                for (int i = 0; i < N; i++) sum += Math.Min(xmin[xbit][i], ymin[ybit][i]) * map[i].p;
                min[cnt] = Math.Min(min[cnt], sum);
            }
            foreach (var m in min) Console.WriteLine(m);
        }

    }
}

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i++)
#define repran(i, a,b) for (int i = a; i<b;i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;
using LP = pair<ll,ll>;
using P = pair<ll,int>;
int n;
ll inf = 1e18;
vector<ll> solve(int n, vector<int> x, vector<int> y, vector<int> p){
    //道路を選んだ集落に関してコストの前計算
    vector<vector<ll>> xcost(1<<n, vector<ll>(n)), ycost(1<<n, vector<ll>(n));
    rep(i, 1<<n){
        rep(j, n){
            xcost[i][j] = abs(x[j]);
            ycost[i][j] = abs(y[j]);
            rep(k, n){
                if ((i>>k) &1){
                   xcost[i][j] = min(xcost[i][j], (ll)abs(x[j]-x[k]));
                   ycost[i][j] = min(ycost[i][j], (ll)abs(y[j]-y[k]));
                }
            }
        }
    }
    rep(i, 1<<n) rep(j, n) {
        xcost[i][j] *= p[j];
        ycost[i][j] *= p[j];
    }

    //各状態に関するmin
    vector<ll> ans(n+1, inf);
    rep(i, 1<<n){
        int cnt = 0;
        rep(j, n){
            if (i>>j &1) ++cnt;
        }
        //iの部分集合に関するmin
        repd(j, i+1){
            j &= i;
            ll cost = 0;
            rep(k, n){
                if (!((i>>k) & 1)){
                    cost += min(xcost[j][k], ycost[i-j][k]);
                }
            }
            ans[cnt] = min(ans[cnt], cost);
        }
    }
    return ans;
}

int main()
{
    cin >> n;
    vector<int> x(n), y(n), p(n);
    rep(i, n) cin >> x[i] >> y[i] >> p[i];
    vector<ll> ans = solve(n, x, y, p);
    rep(i, n+1) cout << ans[i] << endl;
}

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from collections import deque

def solve(n, XYP):
    def convert(x, n=2, k=0):
        A = deque()
        while x:
            x, r = divmod(x, n)
            A.appendleft(r)
        return ''.join(map(str, A)).zfill(k)
    
    def preprocess(n, XYP):
        d_x = {}
        d_y = {}
        for i in range(2**n):
            X, Y = [0], [0]
            for j, (x, y, p) in enumerate(XYP):
                if (i>>j) & 1:
                    X.append(x)
                    Y.append(y)
            Z, W = [], []
            for x, y, p in XYP:
                Z.append(min(abs(x-x_) for x_ in X) * p)
                W.append(min(abs(y-y_) for y_ in Y) * p) 
            d_x[str(X)] = Z
            d_y[str(Y)] = W
        return d_x, d_y
    d_x, d_y = preprocess(n, XYP)
    
    A = defaultdict(lambda:1<<64)
    for i in range(3**n):
        S = list(map(int, bin(i)))
        c = 0
        X, Y = [0], [0]
#         for s, (x, y, p) in zip(S, XYP):
#             if s == 1:
#                 X.append(x)
#                 c += 1
#             elif s == 2:
#                 Y.append(y)
#                 c += 1
#         s = sum(min(d_x[str(X)][j], d_y[str(Y)][j]) for j in range(n))
#         if A[c] > s:
#             A[c] = s
#     for i in range(n+1):
#         print(A[i])

n, *XYP = map(int, open(0).read().split())
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))
solve(n, XYP)

Submission status: Runtime Error

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

# TLE

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

def main():

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

    def abs(N):
        if N >= 0:
            return N
        else:
            return -N

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

    preCalRange = 1 << N

    horizontalLineDistance = []
    verticalLineDistance = []

    for i in range(preCalRange):
        railRoad = bin(i)[2:]
        railRoad = '0' * (N - len(railRoad)) + railRoad
        horizontalLineDistance.append([])
        verticalLineDistance.append([])
        for j in range(N):
            horizontalLineDistance[i].append(min(abs(Resident[j][0]),abs(Resident[j][1])))
            verticalLineDistance[i].append(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]) < horizontalLineDistance[i][j]:
                    horizontalLineDistance[i][j] = abs(Resident[j][0] - Resident[k][0])
                if railRoad[k] == '1' and abs(Resident[j][1] - Resident[k][1]) < verticalLineDistance[i][j]:
                    verticalLineDistance[i][j] = abs(Resident[j][1] - Resident[k][1])

    totalCases = 3 ** N
    power2 = [1]
    for i in range(N):
        power2.append(power2[-1] * 2)
    for i in range(1 << N):
        numNewRailroad = bin(i)[2:].count('1')
        for j in range(i,-1,-1):
            j &= i
            goodList1 = horizontalLineDistance[j]
            goodList2 = verticalLineDistance[i - j]
            for k in range(N):
                minDistance.append(min(goodList1[k], goodList2[k]))
            cost = 0
            for k in range(N):
                cost += Resident[k][2] * minDistance[k]
            if minCost[numNewRailroad] == -1 or minCost[numNewRailroad] > cost:
                minCost[numNewRailroad] = cost
    for elem in minCost:
        print(elem)

main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from collections import deque

def solve(n, XYP):
    def convert(x, n=2, k=0):
        A = deque()
        while x:
            x, r = divmod(x, n)
            A.appendleft(r)
        return ''.join(map(str, A)).zfill(k)
    
    def preprocess(n, XYP):
        d_x = {}
        d_y = {}
        for i in range(2**n):
            X, Y = [0], [0]
            for j, (x, y, p) in enumerate(XYP):
                if (i>>j) & 1:
                    X.append(x)
                    Y.append(y)
            Z, W = [], []
            for x, y, p in XYP:
                Z.append(min(abs(x-x_) for x_ in X) * p)
                W.append(min(abs(y-y_) for y_ in Y) * p) 
            d_x[str(X)] = Z
            d_y[str(Y)] = W
        return dx, dy
    d_x, d_y = preprocess(n, XYP)
    
    A = defaultdict(lambda:1<<64)
    for i in range(3**n):
        S = list(map(int, convert(i, 3, n)))
        c = 0
        X, Y = [0], [0]
        for s, (x, y, p) in zip(S, XYP):
            if s == 1:
                X.append(x)
                c += 1
            elif s == 2:
                Y.append(y)
                c += 1
        s = sum(min(d_x[str(X)][j], d_y[str(Y)][j]) for j in range(n))
        if A[c] > s:
            A[c] = s
    for i in range(n+1):
        print(A[i])

n, *XYP = map(int, open(0).read().split())
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))
solve(n, XYP)

Submission status: Runtime Error

Solution code:
import itertools
N = int(input())
cities = []
S = 0
for _ in range(N):
    city = [int(i) for i in input().split()]
    cities.append(city)
    S += city[2]*min(abs(city[0]),abs(city[1]))
print(S)
for i in range(1,N):
    a = 0
    for j in range(i+1):
        for x in itertools.combinations(range(N),j):
            z = 0
            x = list(x)
            rest = []
            for k in range(N):
                if not k in x:
                    rest.append(k)
            for y in itertools.combinations(rest,i-j):
                draft = 0
                x = [cities[k][0] for k in x]
                y = [cities[k][1] for k in list(y)]
                for city in cities:
                    dx = float("inf")
                    dy = float("inf")
                    if x:
                        dx = min([abs(city[0]-k) for k in x])
                    if y:
                        dy = min([abs(city[1]-k) for k in y])
                    draft += city[2]*(min(abs(city[0]),abs(city[1])) - min(abs(city[0]),abs(city[1]),dx,dy))
                a = max(a,draft)
                if S == a:
                    z = 1
                    break
            if z:
                break
    print(S-a)
    if S == a:
        for _ in range(N-i-1):
            print(0)
        break
print(0)

Submission status: Runtime Error

Solution code:
import sys
import itertools
import operator


def calc_distance(xyp, x_lines, y_lines):
    return sum(p * min(itertools.chain(
        (abs(x - v) for v in x_lines),
        (abs(y - v) for v in y_lines),
        )) for x, y, p in xyp)


def resolve(in_, out):
    n = int(next(in_))
    xyp = tuple(tuple(map(int, (line.split()))) for line in in_)

    print(calc_distance(xyp, [0], [0]), file=out)

    d = []
    for x in range(-15, 16):
        if x == 0:
            continue
        d.append(calc_distance(xyp, [0, x], [0]))
    for y in range(-15, 16):
        if y == 0:
            continue
        d.append(calc_distance(xyp, [0], [0, y]))
    print(min(d), file=out)

    x_all_lines = frozenset(('x', x) for x, y, p in xyp)
    y_all_lines = frozenset(('y', y) for x, y ,p in xyp)
    all_lines = x_all_lines | y_all_lines

    for i in range(2, n + 1):
        d = []
        for lines in itertools.combinations(all_lines, i):
            x_lines = [0]
            y_lines = [0]
            for line in lines:
                if line[0] == 'x':
                    x_lines.append(line[1])
                else:
                    y_lines.append(line[1])
            d.append(calc_distance(xyp, x_lines, y_lines))
        print(min(d), file=out)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def convert(x, n=2, k=0):
    A = []
    while x:
        x, r = divmod(x, n)
        A.append(r)
    return ''.join(map(str, reversed(A))).zfill(k)

n, *XYP = map(int, open(0).read().split())
XYP = list(zip(XYP[::3], XYP[1::3], XYP[2::3]))
A = defaultdict(lambda: float('inf'))
dx = {}
dy = {}
for i in range(2**n):
    X = [0]
    Y = [0]
    for j, (x, y, p) in enumerate(XYP):
        if (i>>j) & 1:
            X.append(x)
            Y.append(y)
    xk = str(sorted(set(X)))
    yk = str(sorted(set(Y)))
    Z = []
    W = []
    for x, y, p in XYP:
        Z.append(min(abs(x-x_) for x_ in X) * p)
        W.append(min(abs(y-y_) for y_ in Y) * p)
    dx[xk] = Z        
    dy[yk] = W

for i in range(3**n):
    X = [0]
    Y = [0]
    S = convert(i, 3, n)
    c = S.count('1') + S.count('2')
    for j, (x, y, p) in enumerate(XYP):
        if S[j] == '1':
            X.append(x)
        elif S[j] == '2':
            Y.append(y)
    xk = str(sorted(set(X)))
    yk = str(sorted(set(X)))
    s = 0
    for i in range(n):
        s += min(dx[xk][i], dy[yk][i])
    if A[c] > s:
        A[c] = s
for i in range(n+1):
    print(A[i])

Submission status: Runtime Error

Solution code:
import sys
import itertools
import operator


def calc_distance(xyp, x_lines, y_lines):
    return sum(p * min(itertools.chain(
        (abs(x - v) for v in x_lines),
        (abs(y - v) for v in y_lines),
        )) for x, y, p in xyp)


def resolve(in_, out):
    n = int(next(in_))
    xyp = tuple(tuple(map(int, (line.split()))) for line in in_)

    x_all_lines = frozenset(('x', x) for x, y, p in xyp if x != 0)
    y_all_lines = frozenset(('y', y) for x, y ,p in xyp if y != 0)
    all_lines = x_all_lines | y_all_lines
    print(calc_distance(xyp, [0], [0]), file=out)

    for i in range(1, n + 1):
        d = []
        for lines in itertools.combinations(all_lines, i):
            x_lines = [0]
            y_lines = [0]
            for line in lines:
                if line[0] == 'x':
                    x_lines.append(line[1])
                else:
                    y_lines.append(line[1])
            d.append(calc_distance(xyp, x_lines, y_lines))
        print(min(d), file=out)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import itertools
import operator


def calc_distance(xyp, x_lines, y_lines):
    return sum(p * min(itertools.chain(
        (abs(x - v) for v in x_lines),
        (abs(y - v) for v in y_lines),
        )) for x, y, p in xyp)


def resolve(in_, out):
    n = int(next(in_))
    xyp = tuple(tuple(map(int, (line.split()))) for line in in_)

    x_all_lines = frozenset(('x', x) for x, y, p in xyp)
    y_all_lines = frozenset(('y', y) for x, y ,p in xyp)
    all_lines = x_all_lines | y_all_lines
    print(calc_distance(xyp, [0], [0]), file=out)

    for i in range(1, n + 1):
        d = []
        for lines in itertools.combinations(all_lines, i):
            x_lines = [0]
            y_lines = [0]
            for line in lines:
                if line[0] == 'x':
                    x_lines.append(line[1])
                else:
                    y_lines.append(line[1])
            d.append(calc_distance(xyp, x_lines, y_lines))
        print(min(d), file=out)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

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

idle_max=10**18

def main(Xlst,Ylst):
    sumc=0
    for x,y,p in XYP:
        c=idle_max
        for X in Xlst:
            c=min(round(abs(X-x))*p,c)
        for Y in Ylst:
            c=min(round(abs(Y-y))*p,c)
        sumc+=c
    return (sumc)

scorelst=[idle_max for i in range(N)]
for bit in list(product(range(2), repeat=N-1)):
    Xlst=[0]
    Ylst=[0]
    for l in range(N):
        score=idle_max
        if bit[l]:
            reX=idle_max
            for n in range(N):
                x,y,p=XYP[n]
                tempXlst=copy.copy(Xlst)
                tempXlst.append(x)
                _score=main(tempXlst,Ylst)
                if _score<score:
                    reX=x
                    score=_score
                    scorelst[l]=min(scorelst[l],_score)
            Xlst.append(reX)
        else:
            reY=idle_max
            for n in range(N):
                x,y,p=XYP[n]
                tempYlst=copy.copy(Ylst)
                tempYlst.append(y)
                _score=main(Xlst,tempYlst)
                if _score<score:
                    reY=y
                    score=_score
                    scorelst[l]=min(scorelst[l],_score)
            Ylst.append(reY)
    #print(bit,Xlst,Ylst)
print(main([0],[0]))
for score in scorelst:
    print(score)

Submission status: Runtime Error

Solution code:
    n = int(input())
    xyp = []
    XY = [(0, 0), (0, 1)]
    for _ in range(n):
        x, y, p = map(int, input().split())
        xyp.append((x, y, p))
        XY.append((x, 0))
        XY.append((y, 1))

    anss = [10**9] * (n+1)
    from itertools import combinations
    for nn in range(n):
        for xy in combinations(XY, nn):
            x_trains = [0]
            y_trains = [0]
            for corr, r in xy:
                if r == 0:
                    x_trains.append(corr)
                else:
                    y_trains.append(corr)

            cost = 0
            for x, y, p in xyp:
                x_dist = min(map(lambda xx: abs(xx-x), x_trains))
                y_dist = min(map(lambda yy: abs(yy-y), y_trains))
                cost += min(x_dist, y_dist)*p
                if anss[nn] < cost:
                    break
            anss[nn] = min(anss[nn], cost)

    for ans in anss:
        if ans == 10**9:
            print(0)
        else:
            print(ans)

Submission status: Runtime Error

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

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

from copy import copy

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)

preCalRange = 1 << N

horizontalLineDistance = []
verticalLineDistance = []

for i in xrange(preCalRange):
    railRoad = []
    tmp = i
    for j in range(N):
        railRoad.append(tmp % 2)
        tmp //= 2
    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])
    horizontalLineDistance.append(copy(minDistance))
    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][1] - Resident[k][1]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][1] - Resident[k][1])
    verticalLineDistance.append(copy(minDistance))

totalCases = 3 ** N

for i in xrange(totalCases):
    railRoad = []
    tmp = i
    for j in range(N):
        railRoad.append(tmp % 3)
        tmp //= 3
    horizontalCount = 0
    verticalCount = 0
    numNewRailroad = 0
    for j in range(N):
        if railRoad[j] == 1:
            numNewRailroad += 1
            horizontalCount += 1 << j
        if railRoad[j] == 2:
            verticalCount += 1 << j
            numNewRailroad += 1
    minDistance = []
    for j in range(N):
        minDistance.append(min(horizontalLineDistance[horizontalCount][j], verticalLineDistance[verticalCount][j]))

    cost = 0
    for j in range(N):
        cost += Resident[j][2] * minDistance[j]
    if minCost[numNewRailroad] == -1 or minCost[numNewRailroad] > cost:
        minCost[numNewRailroad] = cost
for elem in minCost:
    print(elem)

Submission status: Runtime Error

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n = k()
plane = deque([[] for i in range(2000001)])
num = []

for i in range(n):
    a,b,c=map(str,input().split())
    b = int(b)
    if c == "U" or c =- "R":
        b = -b
    plane[0][int(a)].append(b)

for i in range(2000001):
    x = plane[i].popleft()
    if len(x) > 1: