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: Wrong Answer

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
xyp = []
for i in range(N):
    xyp.append(LI())
# xyp = sorted(xyp, key=lambda xyp: xyp[2], reverse= True)
def cal_work(x_lines, y_lines):
    work = 0
    for i in range(N):
        min_dis = mod
        x, y, p = xyp[i]
        for x_line in x_lines:
            min_dis = min(min_dis, abs(x_line - x))
            if min_dis == 0:
                break
        for y_line in y_lines:
            min_dis = min(min_dis, abs(y_line - y))
            if min_dis == 0:
                break
        work += min_dis * p
    return work

def n2kdigit(n,k):
    digits = [0 for i in range(N)]
    cnt = 0
    while n > 0:
        digits[cnt]= n % k
        n = n // k
        cnt += 1
    return digits

anss = [mod for i in range(N + 1)]
for i in range(3 ** N):
    digits = n2kdigit(i, 3)
    x_lines = [0]
    y_lines = [0]
    for i, digit in enumerate(digits):
        if digit == 0:
            pass
        elif digit == 1:
            x_lines.append(xyp[i][0])
        else:
            y_lines.append(xyp[i][1])
            
    cnt = len(x_lines) + len(y_lines) - 2
    anss[cnt] = min(anss[cnt], cal_work(x_lines, y_lines))

for ans in anss:
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from itertools import combinations

n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
x = set(p[i][0] for i in range(n))
y = set(p[i][1] for i in range(n))
X = list(x)
Y = list(y)
a = len(X)
b = len(Y)
m = min(a, b)
for i in range(m):
    cost = 10**9
    for j in combinations(range(a + b), i):
        c = 0
        nx = [0]
        ny = [0]
        for k in j:
            if k < a:
                nx.append(X[k])
            else:
                ny.append(Y[k - a])
        for ps in p:
            c += (min(min(abs(ps[0] - i)
                          for i in nx), min(abs(ps[1] - i)
                                            for i in ny)) * ps[2])
        cost = min(cost, c)
    print(cost)

for i in range(n - m + 1):
    print(0)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
village = []
for i in range(N):
    Xi, Yi, Pi = map(int, input().split())
    village.append((Xi, Yi, Pi))    

def score(X, Y):
    # main_street
    X.append(0)
    Y.append(0)
    s = 0
    for v in village:
        min_dist = 100000
        for x in X:
            if abs(v[0] - x) < min_dist:
                min_dist = abs(v[0] - x)
        for y in Y:
            if abs(v[1] - y) < min_dist:
                min_dist = abs(v[1] - y)
        # print(v, min_dist)
        s += v[2] * min_dist
    return s

candidate = set()
for v in village:
    candidate.add((v[0], 0))
    candidate.add((0, v[1]))

m = score([], [])
for k in range(N + 1):
    min_score = m
    for streets in itertools.combinations(candidate, k):
        X = []
        Y = []
        for street in streets:
            if street[0] == 0:
                Y.append(street[1])
            if street[1] == 0:
                X.append(street[0])
        s = score(X, Y)
        # print(streets, s)
        if s < min_score:
            min_score = s
    print(min_score)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
xyp = []
for i in range(N):
    xyp.append(LI())



xyp = sorted(xyp, key=lambda xyp: xyp[2], reverse= True)

def cal_work(x_lines, y_lines):
    work = 0
    for i in range(N):
        min_dis = mod
        x, y, p = xyp[i]

        for x_line in x_lines:
            min_dis = min(min_dis, abs(x_line - x))
        for y_line in y_lines:
            min_dis = min(min_dis, abs(y_line - y))
        work += min_dis * p
    return work



def n2kdigit(n,k):
    digits = [0 for i in range(N)]
    cnt = 0
    while n > 0:
        digits[cnt]= n % k
        n = n // k
        cnt += 1
    return digits


anss = [mod for i in range(N + 1)]
for i in range(3 ** N):
    digits = n2kdigit(i, 3)
    x_lines = [0]
    y_lines = [0]
    for i, digit in enumerate(digits):
        if digit == 0:
            pass
        elif digit == 1:
            x_lines.append(xyp[i][0])
        else:
            y_lines.append(xyp[i][1])
    
    cnt = len(x_lines) + len(y_lines) - 2
    anss[cnt] = min(anss[cnt], cal_work(x_lines, y_lines))

for ans in anss:
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
C=[]
for i in range(n):
    x,y,p=map(int,input().split())
    C.append((x,y,p))

def calc(city_n,tup,n):
    city=C[city_n]
    xmin=abs(city[0])
    for i in tup:
        if i < n:
            xmin=min(xmin,abs(city[0]-C[i][0]))
    ymin=abs(city[1])
    for i in tup:
        if i >=n:
            ymin=min(ymin,abs(city[1]-C[i-n][1]))
    return min(xmin,ymin)*city[2]

import itertools


for q in range(n+1):
    itr=itertools.combinations(range(n*2),q)
    ans=10**7
    for kumi in itr:
        cal=0
        for i in range(n):
            #print(i,kumi,calc(i,kumi,n))
            cal+=calc(i,kumi,n)
        ans=min(ans,cal)
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=tuple(tuple(map(int,input().split())) for i in range(n))
ans=sum(min(abs(x),abs(y))*p  for x,y,p in l)
minl=[min(abs(x),abs(y)) for x,y,p in l]
max_=min(len(set(x for x,y,p in l)),len(set(y for x,y,p in l)))
print(ans)
for _ in range(n):
    if _+1>=max_:print(0);continue
    g=0
    xans=ans
    for j in range(-10000,0):
        o=sum(min(minl[i],abs(x-j))*p for i,(x,y,p) in enumerate(l))
        if o<xans:g=j;xans=o
    for j in range(1,10001):
        o=sum(min(minl[i],abs(x-j))*p for i,(x,y,p) in enumerate(l))
        if o<xans:g=j;xans=o
    yans=ans
    gg=0
    for j in range(-10000,0):
        o=sum(min(minl[i],abs(y-j))*p for i,(x,y,p) in enumerate(l))
        if o<yans:gg=j;yans=o
    for j in range(1,10001):
        o=sum(min(minl[i],abs(y-j))*p for i,(x,y,p) in enumerate(l))
        if o<yans:gg=j;yans=o
    if xans>yans:
        print(yans)
        for i,(x,y,p)in enumerate(l):
            minl[i]=min(minl[i],abs(y-gg))
        ans=yans
    else:
        print(xans)
        for i,(x,y,p)in enumerate(l):
            minl[i]=min(minl[i],abs(x-g))
        ans=xans

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
X={}
Y={}

LX=[0]
LY=[0]
for i in range(N):
    x,y,p=map(int,input().split())
    L.append([x,y,p])
    if x not in X:
        X[x]=p
    else:
        X[x]+=p
    if y not in Y:
        Y[y]=p
    else:
        Y[y]+=p

#print(X,Y)

ans=[]
cnt=0
for i in range(N):
    cnt+=min(abs(L[i][0]),abs(L[i][1]))*L[i][2]
ans.append(cnt)
#print(ans)
for i in range(N):
    Xmax=0
    Xkey=0
    for k,v in X.items():
        if Xmax<v:
            Xmax=v
            Xkey=k
    Ymax=0
    Ykey=0
    for k,v in Y.items():
        if Ymax<v:
            Ymax=v
            Ykey=k
    if Xmax>Ymax:
        LX.append(Xkey)
        for q in range(N):
            if L[q][0]==Xkey:
                L[q]=[0,0,0]
        
    else:
        LY.append(Ykey)
        for q in range(N):
            if L[q][1]==Ykey:
                L[q]=[0,0,0]
    X={}
    Y={}
    for q in range(N):
        if L[q][0] not in X:
            X[L[q][0]]=L[q][2]
        else:
            X[L[q][0]]+=L[q][2]
        if L[q][1] not in Y:
            Y[L[q][1]]=L[q][2]
        else:
            Y[L[q][1]]+=L[q][2]
    cnt=0
    for l in range(N):
        mlen=10**20
        for x in range(len(LX)):
            if mlen>abs(LX[x]-L[l][0]):
                mlen=abs(LX[x]-L[l][0])
        for y in range(len(LY)):
            if mlen>abs(LY[y]-L[l][1]):
                mlen=abs(LY[y]-L[l][1])
        cnt+=mlen*L[l][2]
    ans.append(cnt)

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N = ii()
    P = [tuple(mis()) for _ in range(N)]
    TX = [0]
    TY = [0]
    def getS():
        return sum(min(min(abs(x - tx) for tx in TX), min(abs(y - ty) for ty in TY)) * p for x, y, p in P)
    print(getS())
    for k in range(N):
        i_min = None
        s_min = INF
        t_min = None
        for i in range(len(P)):
            x, y, _ = P[i]
            #
            TX.append(x)
            s = getS()
            if s_min > s:
                i_min = i
                s_min = s
                t_min = (x, None)
            TX.pop()
            #
            TY.append(y)
            s = getS()
            if s_min > s:
                i_min = i
                s_min = s
                t_min = (None, y)
            TY.pop()
        P.pop(i)
        x, y = t_min
        if y is None:
            TX.append(x)
        else:
            TY.append(y)
        print(s_min)












main()

Submission status: Wrong Answer

Solution code:
n=int(input())
C=[]
for i in range(n):
    x,y,p=map(int,input().split())
    C.append((x,y,p))

def calc(city_n,tup,n):
    city=C[city_n]
    xmin=abs(city[0])
    for i in range(n):
        if i in tup:
            xmin=min(xmin,abs(city[0]-C[i][0]))
    ymin=abs(city[1])
    for i in range(n):
        if i+n in tup:
            ymin=min(ymin,abs(city[1]-C[i][1]))
    return min(xmin,ymin)*city[2]

import itertools


for q in range(n+1):
    itr=itertools.combinations(range(n*2),q)
    ans=10**7
    for kumi in itr:
        cal=0
        for i in range(n):
            #print(i,kumi,calc(i,kumi,n))
            cal+=calc(i,kumi,n)
        ans=min(ans,cal)
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xyp = []
x = []
y = []
we = [0]
ns = [0]
stemps = 0
temp = ["x",0]
for i in range(n):
    a,b,c = map(int,input().split())
    xyp.append([a,b,c])
    x.append(a)
    y.append(b)
    stemps += min(abs(a*c),abs(b*c))
print(stemps)
for i in range(n):
    s = 10**18
    for l in x:
        stemps = 0
        for j in xyp:
            temps = 10**16
            for k in we:
                temps = min(temps,abs(j[0]-k)*j[2])
            for k in ns:
                temps = min(temps,abs(j[1]-k)*j[2])
            temps = min(temps,abs(j[0]-l)*j[2])
            stemps += temps
        if stemps < s:
            s = stemps
            temp = ["x",l]
    for l in y:
        stemps = 0
        for j in xyp:
            temps = 10**16
            for k in we:
                temps = min(temps,abs(j[0]-k)*j[2])
            for k in ns:
                temps = min(temps,abs(j[1]-k)*j[2])
            temps = min(temps,abs(j[1]-l)*j[2])
            stemps += temps
        if stemps < s:
            s = stemps
            temp = ["y",l]
    if temp[0] == "x":
        we.append(temp[1])
    else:
        ns.append(temp[1])
    print(s)
# print(ns)
# print(we)
# print(x)
# print(y)
# print(0)
# print(xyp)

Submission status: Wrong Answer

Solution code:
n = int(input())
xyp = []
x = []
y = []
we = [0]
ns = [0]
stemps = 0
temp = ["x",0]
for i in range(n):
    a,b,c = map(int,input().split())
    xyp.append([a,b,c])
    x.append(a)
    y.append(b)
    stemps += min(abs(a*c),abs(b*c))
print(stemps)
for i in range(n):
    s = 10**12
    for l in x:
        stemps = 0
        for j in xyp:
            temps = 10**10
            for k in we:
                temps = min(temps,abs(j[0]-k)*j[2])
            for k in ns:
                temps = min(temps,abs(j[1]-k)*j[2])
            temps = min(temps,abs(j[0]-l)*j[2])
            stemps += temps
        if stemps < s:
            s = stemps
            temp = ["x",l]
    for l in y:
        stemps = 0
        for j in xyp:
            temps = 10**10
            for k in we:
                temps = min(temps,abs(j[0]-k)*j[2])
            for k in ns:
                temps = min(temps,abs(j[1]-k)*j[2])
            temps = min(temps,abs(j[1]-l)*j[2])
            stemps += temps
        if stemps < s:
            s = stemps
            temp = ["y",l]
    if temp[0] == "x":
        we.append(temp[1])
    else:
        ns.append(temp[1])
    print(s)
# print(ns)
# print(we)
# print(x)
# print(y)
# print(0)
# print(xyp)

Submission status: Wrong Answer

Solution code:
N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
INF=10**18+10
DP=[[INF]*N for i in range(3**N)]
DP[0]=[min(abs(X[i][0]),abs(X[i][1]))*X[i][2] for i in range(N)]
Y=[]
Z=[]
def triand(x,y):
  n,m=x,y
  while min(n,m):
    if (n%3)!=0 and (m%3)!=0:
      return 1
    n,m=n//3,m//3
  return 0

def tricount(x):
  n=x
  r=0
  while n:
    if n%3:
      r+=1
    n//=3
  return r
for i in range(3**N):
  for j in range(N):
    if triand(3**j,i)==0:
      Y=DP[i][:]
      Z=DP[i][:]
      for k in range(N):
        Y[k]=min(Y[k],abs(X[k][0]-X[j][0])*X[k][2])
        Z[k]=min(Z[k],abs(X[k][1]-X[j][1])*X[k][2])
      if sum(DP[i+3**j])>sum(Y):
        DP[i+3**j]=Y[:]
      if sum(DP[i+2*3**j])>sum(Z):
        DP[i+3**j]=Z[:]
P=[INF]*(N+1)
for i in range(3**N):
  P[tricount(i)]=min(P[tricount(i)],sum(DP[i]))
print(*P,sep='\n')

Submission status: Wrong Answer

Solution code:
n = int(input())
xyp = [list(map(int, input().split())) for i in range(n)]
inf = 1<<32
tate = [[] for i in range(1<<n)]
yoko = [[] for i in range(1<<n)]
for state in range(1<<n):
    tmp_x = [0]
    tmp_y = [0]
    for i in range(n):
        if state & (1<<i):
            tmp_x.append(xyp[i][0])
            tmp_y.append(xyp[i][1])
    x_score = [0]*n
    y_score = [0]*n
    for i, (x,y,p) in enumerate(xyp):
        x_m = min(abs(x-xi) for xi in tmp_x)
        y_m = min(abs(y-yi) for yi in tmp_y)
        x_score[i] = x_m * p
        y_score[i] = y_m * p
    tate[state] = x_score
    yoko[state] = y_score

ans = [inf]*(1<<n)
for state in range(1<<n):
     j = state
     while j>=0:
        j &= state
        i = state^j
        tmp1 = sum(min(tate[i][k], yoko[j][k]) for k in range(n))
        if tmp1 < ans[state]:
            ans[state] = tmp1 
        j -= 1

cnt = [0]*(1<<n)
for i in range(1<<(n-1)):
    cnt[2*i] = cnt[i]
    cnt[2*i+1] = cnt[i]+1

ans_k = [inf]*(n+1)
for state in range(1<<n):
    k = cnt[state]
    if ans_k[k] > ans[state]:
        ans_k[k] = ans[state]
print(*ans_k, sep="\n")

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

for K in range(N+1):
    minwalksum = 10 ** 9
    for stations in combinations(range(N), K):
        for i in range(1 << K):
            xs = [0]
            ys = [0]
            for j in range(K):
                if i & (1 << j):
                    xs.append(XYPs[stations[j]][0])
                else:
                    ys.append(XYPs[stations[j]][1])
            walksum = 0
            for X, Y, P in XYPs:
                mindis = min(min([abs(X - x) for x in xs]), min([abs(Y - y) for y in ys]))
                walksum += mindis * P
            minwalksum = min(minwalksum, walksum)
    print(minwalksum)

Submission status: Wrong Answer

Solution code:
N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
INF=10**18+10
DP=[[INF]*N for i in range(1<<N)]
R=sorted([i for i in range(1<<N)],key=lambda x:bin(x).count('1'))
del R[-1]
DP[0]=[min(abs(X[i][0]),abs(X[i][1]))*X[i][2] for i in range(N)]
Y=[]
Z=[]
for i in range(len(R)):
  for j in range(N):
    if (1<<j)&R[i]==0:
      Y=DP[R[i]][:]
      Z=DP[R[i]][:]
      for k in range(N):
        Y[k]=min(Y[k],abs(X[j][0]-X[k][0])*X[k][2])
        Z[k]=min(Z[k],abs(X[j][1]-X[k][1])*X[k][2])
      if sum(DP[R[i]|(1<<j)])>=sum(Y):
        DP[R[i]|(1<<j)]=Y[:]
      if sum(DP[R[i]|(1<<j)])>=sum(Z):
        DP[R[i]|(1<<j)]=Z[:]
P=[INF]*(N+1)
for i in range(1<<N):
  P[bin(i).count('1')]=min(P[bin(i).count('1')],sum(DP[i]))
print(*P,sep='\n')

Submission status: Wrong Answer

Solution code:
N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
INF=10**18+10
DP=[[INF]*N for i in range(1<<N)]
R=sorted([i for i in range(1<<N)],key=lambda x:bin(x).count('1'))
del R[-1]
DP[0]=[min(abs(X[i][0]),abs(X[i][1]))*X[i][2] for i in range(N)]
Y=[]
Z=[]
for i in range(len(R)):
  for j in range(N):
    if (1<<j)&R[i]==0:
      Y=DP[R[i]][:]
      Z=DP[R[i]][:]
      for k in range(N):
        Y[k]=min(Y[k],abs(X[j][0]-X[k][0])*X[k][2])
        Z[k]=min(Z[k],abs(X[j][1]-X[k][1])*X[k][2])
      if sum(DP[R[i]|(1<<j)])>sum(Y):
        DP[R[i]|(1<<j)]=Y[:]
      if sum(DP[R[i]|(1<<j)])>sum(Z):
        DP[R[i]|(1<<j)]=Z[:]
P=[INF]*(N+1)
for i in range(1<<N):
  P[bin(i).count('1')]=min(P[bin(i).count('1')],sum(DP[i]))
print(*P,sep='\n')

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

n = int(input())
X, Y, P = [], [], []
T = []
U = 0
for _ in range(n):
  x, y, p = map(int, input().split())
  X.append(x)
  Y.append(y)
  P.append(p)
  t = min(abs(x), abs(y))
  T.append(t)
  U += p*t
X = tuple(X)
Y = tuple(Y)
P = tuple(P)
T = tuple(T)
L = [U]*(n+1)
mask = (1<<n)-1
def f(Z):
  res = [[U]*(1<<n) for _ in range(n)]
  for j, z in enumerate(Z):
    for i in range(1<<n):
      if i>>j & 1:
        for q in range(n):
          res[q][i] = min(res[q][i], abs(Z[q]-z))
  return res
A, B = f(X), f(Y)
for i in range(1<<n):
  s = i ^ mask
  j = i
  while j:
    temp = 0
    cnt = 0
    for k, p in enumerate(P):
      temp += p*min(A[k][s], B[k][j], T[k])
      if (s>>k & 1) | (j>>k & 1):
        cnt += 1
    L[cnt] = min(L[cnt], temp)
    j = (j-1) & i
  temp = 0
  cnt = 0
  for k, p in enumerate(P):
    temp += p*min(A[k][s], T[k])
    if (s>>k & 1):
      cnt += 1
  L[cnt] = min(L[cnt], temp)
print(*L, sep="\n")

Submission status: Time Limit Exceeded

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

n = int(input())
X, Y, P = [], [], []
T = []
U = 0
for _ in range(n):
  x, y, p = map(int, input().split())
  X.append(x)
  Y.append(y)
  P.append(p)
  t = min(abs(x), abs(y))
  T.append(t)
  U += p*t
X = tuple(X)
Y = tuple(Y)
P = tuple(P)
T = tuple(T)
L = [U]*(n+1)
mask = (1<<n)-1
def f(Z):
  res = [[U]*(1<<n) for _ in range(n)]
  for j, z in enumerate(Z):
    for i in range(1<<n):
      if i>>j & 1:
        for q in range(n):
          res[q][i] = min(res[q][i], abs(Z[q]-z))
  return res
A, B = f(X), f(Y)
for i in range(1<<n):
  s = i ^ mask
  j = s
  while j:
    temp = 0
    cnt = 0
    for k, p in enumerate(P):
      temp += p*min(A[k][i], B[k][j], T[k])
      if (i>>k & 1) | (j>>k & 1):
        cnt += 1
    L[cnt] = min(L[cnt], temp)
    j = (j-1) & s
  temp = 0
  cnt = 0
  for k, p in enumerate(P):
    temp += p*min(A[k][i], T[k])
    if (i>>k & 1):
      cnt += 1
  L[cnt] = min(L[cnt], temp)
print(*L, sep="\n")

Submission status: Time Limit Exceeded

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

n = int(input())
X, Y, P = [], [], []
T = []
U = 0
for _ in range(n):
  x, y, p = map(int, input().split())
  X.append(x)
  Y.append(y)
  P.append(p)
  t = min(abs(x), abs(y))
  T.append(t)
  U += p*t
L = [U]*(n+1)
mask = (1<<n)-1
def f(Z):
  res = [[U]*(1<<n) for _ in range(n)]
  for i in range(1<<n):
    for j, z in enumerate(Z):
      if i>>j & 1:
        for q in range(n):
          res[q][i] = min(res[q][i], abs(Z[q]-z))
  return res
A, B = f(X), f(Y)
for i in range(1<<n):
  s = i ^ mask
  j = s
  while j:
    temp = 0
    cnt = 0
    for k, p in enumerate(P):
      temp += p*min(A[k][i], B[k][j], T[k])
      if (i>>k & 1) | (j>>k & 1):
        cnt += 1
    L[cnt] = min(L[cnt], temp)
    j = (j-1) & s
  temp = 0
  cnt = 0
  for k, p in enumerate(P):
    temp += p*min(A[k][i], T[k])
    if (i>>k & 1):
      cnt += 1
  L[cnt] = min(L[cnt], temp)
print(*L, sep="\n")

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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