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:
import sys
from itertools import product
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]

def calcdist(xyp, Xset, Yset):
    total = 0
    #print("xyp", len(xyp))
    #print(Xset, Yset)
    for i in range(len(xyp)):
        nearest = Xset[0]
        nearestdist = abs(Xset[0]-xyp[i][0])
        nearestisX = True
        for e in Xset[1:]:
            if abs(e-xyp[i][0]) < nearestdist:
                nearest = e
                nearestdist = abs(e-xyp[i][0])
        for e in Yset:
            if abs(e-xyp[i][1]) < nearestdist:
                nearestisX = False
                nearest = e
                nearestdist = abs(e-xyp[i][1])
        #print(nearest, nearestisX)
        if nearestisX:
            total += xyp[i][2]*abs(nearest-xyp[i][0])
        else:
            total += xyp[i][2]*abs(nearest-xyp[i][1])
    return total

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

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

for i in range(N+1):
    combs = list(product(range(2), repeat=N))
    minsum = float('inf')
    if i == 0:
        minsum = calcdist(XYP, [0], [0])
    for c in combs:
        newroadsX = {0}
        newroadsY = {0}
        j= 0
        while len(newroadsX) +len(newroadsY) < i +2 and j < N:
            if c[j]:
                newroadsY.add(XYP[j][1])
            else:
                newroadsX.add(XYP[j][0])
            j += 1
        #if i == 4:
            #print(newroadsX, newroadsY)
        minsum = min(calcdist(XYP, list(newroadsX), list(newroadsY)), minsum)

    print(minsum)

Submission status: Wrong Answer

Solution code:
"""
実は全探索で解けたりする？⇒無理。
一回、すべての集落の市民の数が1であるとして、考えてみる。

集落の数が2つあるとする。
このとき、集落の真ん中に置けばよいか、というとそうでもない。
極端な話、片方の集落がX軸かY軸の上にあれば、その集落のことは考慮する必要はない。

逆に考えた方がいいのかな。N本あるときは、0


各座標の全
問題の味方を変えてみる。

あ、DPで解けるかも
金塊のときのDPに近い。

X軸で分割されたDPとY軸で分割されたDP

座標圧縮で解けないか？

中点に設置する必要はない。
15個の集落のどれに合わせるかを考えればよい。また、縦に合わせるか、横に合わせるかを考えればよい。
候補は常に最大で30しかない。
その30について、実際にシミュレーションすればよい。
y上に集落を構えている数の最大値。
試すパターンは全部で10億ほど。ぎりいけるはず。
"""
from itertools import combinations
N = int(input())
XYP = [list(map(int,input().split())) for _ in range(N)]
candi = set()
for x,y,p in XYP:
    candi.add((x,"X"))
    candi.add((y,"Y"))
candi = list(candi)

#初期状態での合計値を調べる
tmp = 0
for x,y,p in XYP:
    tmp += min(abs(x),abs(y))*p
print(tmp)

for i in range(1,N):
    ans = float("INF")
    for a in list(combinations(candi,i)):
        tmp = 0
        for x,y,p in XYP:
            mini = min(abs(x),abs(y))*p
            for b in a:
                if b[1] == "X":
                    mini = min(mini,abs(b[0]-x)*p)
                else:
                    mini = min(mini,abs(b[0]-y)*p)
            tmp += mini
        ans = min(ans,tmp)
    print(ans)

print(0)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 30
from itertools import combinations
from collections import defaultdict
N = int(input())
XYP = [list(map(int, input().split())) for _ in range(N)]
# X=0,Y=1
origin = [(0, 0), (1, 0)]
XYP.sort(key=lambda x:x[2], reverse=True)
d = defaultdict(int)
X = []
Y = []
all_points = []
for x, y, p in XYP:
    X.append((0,x))
    Y.append((1,y))
    d[(0,x)] += p
    d[(1,y)] += p
zerocnt = min(len(set(X)), len(set(Y)))

d = [[i, d[i]] for i in d.keys()]

for i in sorted(d, key=lambda x: x[1], reverse=True):
    all_points.append(i[0])

def calc(cost):
    ret = 0
    for x, y, p in XYP:
        tmp = INF
        for xory, c in cost:
            if xory == 0:
                tmp = min(tmp, abs(c-x) * p)
            else:
                tmp = min(tmp, abs(c-y) * p)
        ret += tmp
    return ret

pre = 0
print(calc(origin))
for i in range(N):
    cost = INF
    for comb in combinations(all_points[:(i+1)*5], i+1):
        comb = list(comb)
        comb.extend(origin)
        cost = min(cost, calc(comb))
    print(cost)
    pre = i

for i in range(pre+1,N):
    print(0)

Submission status: Wrong Answer

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

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

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


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

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

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


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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
XYP = []
for _ in range(N):
    t = list(map(int,input().split()))
    XYP.append([t[0],t[1],t[2]])

def calc():
    rev = 0
    for i in range(N):
        rev += min(XYP[i][0], XYP[i][1]) * XYP[i][2]
    return rev

sum = float('inf')
for i in range(N+1):
    if sum == 0:
        print(0)
        continue
    
#    if i != 0:
        

    sum += calc()
    print(sum)

Submission status: Wrong Answer

Solution code:
n = int(input())
z = [list(map(int, input().split())) for  _ in range(n)]
kyori = []

#x = [i[0] for i in z]
for i in z:
    if abs(i[0]) >= abs(i[1]):
        kyori.append(abs(i[1]))
    else:
        kyori.append(abs(i[0]))

def check(x, y):
    s = 0
    if x == 0:
        count = 0
        for i in z:
            if kyori[count] > abs(i[1]-y):
                s += abs(i[1]-y) * i[2]
                count += 1
            else:
                s += kyori[count] * i[2]
                count += 1
    else:
        count = 0
        for i in z:
            if kyori[count] > abs(i[0]-x):
                s += abs(i[0]-x) * i[2]
                count += 1
            else:
                s += kyori[count] * i[2]
                count += 1
    return s

def koshin(x, y):
    if x == 0:
        count = 0
        for i in z:
            if kyori[count] > abs(i[1]-y):
                kyori[count] = abs(i[1]-y)
                count += 1
            else:
                count += 1
    else:
        count = 0
        for i in z:
            if kyori[count] > abs(i[0]-x):
                kyori[count] = abs(i[0]-x)
                count += 1
            else:
                count += 1


s = check(0,0)
kakux = 0
kakuy = 0
print(s)
for k in range(n):
    shoki = s
    kakux = 0
    kakuy = 0
    for i in z:
        d = check(i[0],0)
        if shoki > d:
            shoki = d
            kakux = i[0]
            kakuy = 0
        d = check(0,i[1])
        if shoki > d:
            shoki = d
            kakux = 1
            kakuy = 0
    if s != shoki:
        koshin(kakux,kakuy)
    s = shoki
    print(s)

Submission status: Wrong Answer

Solution code:

import itertools as it
#import numpy as np

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def array(size, init=0):
    return [[init for j in range(size[1])] for i in range(size[0])]


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def permutate(x, A):
    n = len(x)
    res = [-1]*n
    for i in range(n):

        res[i] = x[A[i]]
    return res


def generate_bin(digit):
    for b in range(2**digit):
        b = bin(b)
        tmp = b[2:].zfill(digit)
        yield list(map(int, tmp))
        # b=list(map(int,list(b[2:].zfill(digit))))
        # yield b


def search(x, count):
    #print("top", x, count)

    for d in directions:
        nx = d+x
        # print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)

    return count


N = int(input())

shuraku = []
for i in range(N):
    shuraku.append(acinput())

for k in range(0, N+1):
    mincost = 10**9
    #print("k", k)
    for sc in it.combinations(range(0, N), k):
        #print("sc", sc)
        for l in generate_bin(k):
            xx = [0]
            yy = [0]
            # print(l)
            m = 0
            for ssc in sc:
                if l[m] == 0:
                    xx.append(shuraku[ssc][0])
                else:
                    yy.append(shuraku[ssc][1])
                m += 1

            #print("xx", xx, yy)
            cost = 0
            for ss in shuraku:
                #tmpx = np.abs(np.array(xx)-ss[0])
                #tmpy = np.abs(np.array(yy)-ss[1])
                minx = 10**8
                for sx in xx:
                    minx = min(abs(sx-ss[0]), minx)
                miny = 10**8
                for sy in yy:
                    miny = min(abs(sy-ss[1]), miny)

                tmp = min(minx, miny)
                cost += tmp*ss[2]

            mincost = min(cost, mincost)

    print(mincost)

Submission status: Wrong Answer

Solution code:
import itertools
#import bisect

def main():
  N = int(input())
  X = []
  Y = []
  P = []
  for _ in range(N):
    x, y, p = [int(x) for x in input().split()]
    X.append(x)
    Y.append(y)
    P.append(p)
  Ms = [15 * 10000] * (N + 1)
  Mm = [[10000] * N  for _ in range(N+1)]
  
  for selected in itertools.product([0, 1, 2], repeat=N):
    #print(selected)
    LX = sorted([0] + [X[i] for i, s in enumerate(selected) if s == 1])
    LY = sorted([0] + [Y[i] for i, s in enumerate(selected) if s == 2])
    # print(LX, LY)
    
    S = 0
    for i in range(N):
      if selected[i]:
        continue
      M = 10000
      for x in LX:
        M = min(M, abs(x - X[i]))
      for y in LY:
        M = min(M, abs(y - Y[i]))
      S += M * P[i]
    count = sum([ x > 0 for x in selected])
    Ms[count] = min(Ms[count], S)
      
  for m in Ms:
    print(m)
      
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product

INF_D = 100000
N = int(input())
villages = [list(map(int, input().split())) for _ in range(N)]

# 方針 集落と集落の間を通るよりも集落を通り抜ける方が良いのは確実
# 集落を通る鉄道の候補を列挙し、bit全探索する
all_rails = []
for x in set(map(lambda village: village[0], villages)):
    all_rails.append([x, INF_D])
for y in set(map(lambda village: village[1], villages)):
    all_rails.append([INF_D, y])
all_rails_N = len(all_rails)
# print(all_rails)

def S(villages, rails):
    ans = 0
    # print(villages)
    # print(rails)
    for village in villages:
        min_D = INF_D
        X, Y, P = village
        for rail in rails:
            min_D = min(min_D, abs(rail[0]-X), abs(rail[1]-Y))
            if min_D == 0:
                break
        # print(min_D)
        ans += P*min_D
    return ans

K_rails = [[] for _ in range(N+1)]
for rails_bit in product([0, 1], repeat=all_rails_N):
    rails = [all_rails[i] for i in range(all_rails_N) if rails_bit[i]]
    rails_N = len(rails)
    if rails_N <= N:
        K_rails[sum(rails_bit)].append([[0, INF_D], [INF_D, 0]] + rails)
# print(*K_rails, sep='\n')
for i in range(N):
    ans = 10**11
    for rails in K_rails[i]:
        ans = min(ans, S(villages, rails))
    print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy
import itertools
import math

n = int(input())

town = [[] for i in range(n)]

for i in range(n):
  tmp = list(map(int, input().split()))
  city = tmp+[abs(tmp[0]),abs(tmp[1])]
  for c in city:
    town[i].append(c)

town = np.array(town)
x, x_counts = np.unique(town[:,0], return_counts=True)
y, y_counts = np.unique(town[:,1], return_counts=True)
double  = (x_counts-1).sum() + (y_counts-1).sum()

ans = []


for i in range(n+1):

  if False:
  #if i >= n-double:
    ans.append(0)
  else:
    minimum = math.inf
    for v in itertools.combinations(list(range(len(x)+len(y))), i):
      dummy = copy.deepcopy(town)
      tmp_ans = 0
      for l in v:
        if l <= len(x)-1:
          for t in dummy:
            t[3] = min(t[3],abs(t[0]-x[l]))
        else:
          for t in dummy:
            t[4] = min(t[4],abs(t[1]-y[l-len(x)]))

      for t in dummy:
        tmp_ans += min(t[3],t[4])*t[2]

      minimum = min(minimum, tmp_ans)
    ans.append(minimum)

for a in ans:
  print(a)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = []
for i in range(n):
    x,y,p = map(int,readline().split())
    lst1.append([x,y,p])
made = [(0,0)] #(x=1に引いたならば(1,0)みたいな)

used = [0]*n

def funcx(i):
    res = made + [(lst1[i][0],0)]
    ret = 0
    for i in range(n):
        loss = 10**24
        for j in range(len(res)):
            x = min(abs(res[j][0]-lst1[i][0]),abs(lst1[i][0]-res[j][0]))
            y = min(abs(res[j][1]-lst1[i][1]),abs(lst1[i][1]-res[j][1]))
            loss = min(loss,lst1[i][2]*min(x,y))
        ret += loss
    return ret

def funcy(i):
    res = made + [(0,lst1[i][1])]
    ret = 0
    for i in range(n):
        loss = 10**24
        for j in range(len(res)):
            x = min(abs(res[j][0]-lst1[i][0]),abs(lst1[i][0]-res[j][0]))
            y = min(abs(res[j][1]-lst1[i][1]),abs(lst1[i][1]-res[j][1]))
            loss = min(loss,lst1[i][2]*min(x,y))
        ret += loss
    return ret

#初回手動
ret = 0
res = made
for i in range(n):
    loss = 10**24
    for j in range(len(res)):
        x = min(abs(res[j][0]-lst1[i][0]),abs(lst1[i][0]-res[j][0]))
        y = min(abs(res[j][1]-lst1[i][1]),abs(lst1[i][1]-res[j][1]))
        loss = min(loss,lst1[i][2]*min(x,y))
    ret += loss
print(ret)

mura = 0
for i in range(n): #各路線について
    minloss = 10**24
    kouho = (0,0)
    for j in range(n): #各村について
        #x軸アプローチ
        res1 = funcx(j)
        #y軸アプローチ
        res2 = funcy(j)
        if res1<res2:
            if res1 < minloss:
                minloss = res1
                kouho = (lst1[j][0],0)
                mura = j
        else:
            if res2 < minloss:
                minloss = res2
                kouho = (0,lst1[j][1])
    made.append(kouho)
    print(minloss)

Submission status: Wrong Answer

Solution code:
n=int(input(""))
lis=[]
for i in range(n):
    t=input("").split(" ")
    lis+=[[int(t[0]),int(t[1]),int(t[2])]]
listx=[]
listy=[]
for i in lis:
    listx+=[i[0]]
    listy+=[i[1]]

listxy=[[0,1]]*n

def ch(x,sgn):
    sam=0
    lisss=[]
    for i in range(n):
        if(listxy[i][1]==1):
            ttt=abs(lis[i][0]-listxy[i][0])
        else:
            ttt=abs(lis[i][1]-listxy[i][0])
        if(sgn==1):
            sss=abs(lis[i][0]-x)
        else:
            sss=abs(lis[i][1]-x)
        if(sss<ttt):
            lisss+=[i]
            sam+=(ttt-sss)*lis[i][2]

    return sam,lisss
samsam=0      
for i in range(n):
        if(listxy[i][1]==1):
            ttt=abs(lis[i][0]-listxy[i][0])
        else:
            ttt=abs(lis[i][1]-listxy[i][0])
        samsam+=ttt*lis[i][2]
print(samsam)
for i in range(1,n+1):
    maxt=0
    listtmp=[]
    sgn=0
    kkk=0
    for k in listx:
        ta,tb=ch(k,1)
        if(ta>maxt):
            maxt=ta
            kkk=k
            sgn=1
            listtmp=tb
    for k in listy:
        ta,tb=ch(k,-1)
        if(ta>maxt):
            maxt=ta
            sgn=-1
            kkk=k
            listtmp=tb
    if(sgn==0):
        print(samsam)
        continue
    for i in listtmp:
        listxy[i]=[kkk,sgn]
    samsam-=maxt
    print(samsam)

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy
import itertools
import math

n = int(input())

town = [[] for i in range(n)]

for i in range(n):
  tmp = list(map(int, input().split()))
  city = tmp+[abs(tmp[0]),abs(tmp[1])]
  for c in city:
    town[i].append(c)

town = np.array(town)
x, x_counts = np.unique(town[:,0], return_counts=True)
y, y_counts = np.unique(town[:,1], return_counts=True)
double  = (x_counts-1).sum() + (y_counts-1).sum()

ans = []

print(x,y)

for i in range(n+1):

  if False:
  #if i >= n-double:
    ans.append(0)
  else:
    minimum = math.inf
    for v in itertools.combinations(list(range(len(x)+len(y))), i):
      dummy = copy.deepcopy(town)
      tmp_ans = 0
      for l in v:
        if l <= len(x)-1:
          for t in dummy:
            t[3] = min(t[3],abs(t[0]-x[l]))
        else:
          for t in dummy:
            t[4] = min(t[4],abs(t[1]-y[l-len(x)]))

      for t in dummy:
        tmp_ans += min(t[3],t[4])*t[2]

      minimum = min(minimum, tmp_ans)
    ans.append(minimum)

for a in ans:
  print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())
xyp=[list(map(int,input().split())) for i in range(n)]

from itertools import *

xset=set()
yset=set()
for x,y,p in xyp:
    xset.add(x)
    yset.add(y)

lenx=len(xset)
leny=len(yset)

uniqx=list(xset)
uniqy=list(yset)

uniqx.sort()
uniqy.sort()
for i in range(n+1): # draw i line
    if i>=lenx or i>=leny:
        print(0)
        continue

    ans=10**10
    for tate in range(lenx+1):
        yoko = i-tate
        if yoko<0:
            continue

        for tates in combinations(uniqx,tate):
            for yokos in combinations(uniqy,yoko):
                cur = 0
                for x,y,p in xyp:
                    if x in tates or y in yokos:
                        continue
                    else:
                        mindis = min(abs(x),abs(y))
                        for tmp in tates:
                            mindis=min(mindis,abs(x-tmp))
                        for tmp in yokos:
                            mindis=min(mindis,abs(y-tmp))
                        cur+=mindis*p

                ans=min(ans,cur)

    print(ans)

Submission status: Wrong Answer

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())
    X, Y, P = [], [], []
    dist = 0
    INF = 1 << 50
    hline = [0]
    vline = [0]
    for i in range(N):
        x,y,p = map(int, sysread().split())
        X.append(x)
        Y.append(y)
        P.append(p)
        dist += min(abs(x), abs(y)) * p

    Xmin = min(X)
    Xmax = max(X)
    Ymin = min(Y)
    Ymax = max(Y)
    best_dist = dist

    print(best_dist)
    for i in range(N):
        dist_x, dist_y = INF, INF
        x_, y_ = None, None
        for j in range(Xmin, Xmax+1):
            dist_ = 0
            for k in range(N):
                _dx = min([abs(v-X[k]) for v in vline+[j]])
                _dy = min([abs(h-Y[k]) for h in hline])
                _d = min(_dx, _dy) * P[k]
                dist_ += _d
            if dist_x > dist_:
                dist_x = dist_
                x_ = j

        for j in range(Ymin, Ymax+1):
            dist_ = 0
            for k in range(N):
                _dx = min([abs(v-X[k]) for v in vline])
                _dy = min([abs(h-Y[k]) for h in hline + [j]])
                _d = min(_dx, _dy) * P[k]
                dist_ += _d
            if dist_y > dist_:
                dist_y = dist_
                y_ = j
        if dist_x > dist_y:
            hline.append(y_)
            best_dist = dist_y
        else:
            vline.append(x_)
            best_dist = dist_x

        print(best_dist)






if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
n=int(input())
for _ in range(n):
  print(0)

Submission status: Wrong Answer

Solution code:
from itertools import product
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
S = sorted([(A[i][2],i) for i in range(N)],key=lambda x:x[0],reverse=True)
for K in range(N+1):
    cmin = 10**12
    for x in product((0,1),repeat=K):
        B = [S[i][1] for i in range(K)]
        X = [0]
        Y = [0]
        for i in range(K):
            if x[i]==0:
                X.append(A[B[i]][0])
            else:
                Y.append(A[B[i]][1])
        cnt = 0
        for i in range(N):
            x,y,p = A[i]
            xmin = 10**4+10
            for a in X:
                xmin = min(xmin,abs(x-a))
            ymin = 10**4+10
            for b in Y:
                ymin = min(ymin,abs(y-b))
            cnt += min(xmin,ymin)*p
        cmin = min(cmin,cnt)
    print(cmin)

Submission status: Wrong Answer

Solution code:
class Pt(object):
    def __init__(self, x, y, p) -> None:
        self.x = x
        self.y = y
        self.p = p
        self.d = min(abs(x), abs(y))


def calc_cost(lst_pt, idx):
    cst = 0
    if idx is None:
        for pt in lst_pt:
            cst += pt.p * pt.d
        return cst

    cst_x = 0
    for pt in lst_pt:
        if pt.d == 0:
            continue
        d_x = abs(pt.x - lst_pt[idx].x)
        cst_x += pt.p * min(pt.d, d_x)

    cst_y = 0
    for pt in lst_pt:
        if pt.d == 0:
            continue
        d_y = abs(pt.y - lst_pt[idx].y)
        cst_y += pt.p * min(pt.d, d_y)
    cst = min(cst_x, cst_y)

    return cst


def update_pt(lst_pt, idx):
    for i, pt in enumerate(lst_pt):
        if pt.d == 0:
            continue
        d_x = abs(pt.x - lst_pt[idx].x)
        d_y = abs(pt.y - lst_pt[idx].y)
        pt.d = min(pt.d, d_x, d_y)
        lst_pt[i] = pt
    return lst_pt


def main():
    n = int(input())
    lst_pt = []
    lst_d = []
    for _ in range(n):
        x, y, p = [int(v) for v in input().split(' ')]
        lst_pt.append(Pt(x, y, p))
        lst_d.append(min(x, y))

    fin_flag = False
    min_cst = calc_cost(lst_pt, None)
    print(min_cst)
    for _ in range(n):
        if fin_flag:
            print(0)
            continue

        min_idx = None
        for i in range(n):
            if lst_pt[i].d == 0:
                continue
            cst = calc_cost(lst_pt, i)
            if min_cst is None or min_cst > cst:
                min_idx = i
                min_cst = cst

        if min_idx is not None:
            lst_pt = update_pt(lst_pt, min_idx)
        print(min_cst)
        fin_flag = min_cst == 0


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = []
for i in range(n):
    x,y,p = map(int,readline().split())
    lst1.append([x,y,p])
made = [(0,0)] #(x=1に引いたならば(1,0)みたいな)

used = [0]*n

def funcx(i):
    res = made + [(lst1[i][0],0)]
    ret = 0
    for i in range(n):
        loss = 10**24
        for j in range(len(res)):
            x = min(abs(res[j][0]-lst1[i][0]),abs(lst1[i][0]-res[j][0]))
            y = min(abs(res[j][1]-lst1[i][1]),abs(lst1[i][1]-res[j][1]))
            loss = min(loss,lst1[i][2]*min(x,y))
        ret += loss
    return ret

def funcy(i):
    res = made + [(0,lst1[i][1])]
    ret = 0
    for i in range(n):
        loss = 10**24
        for j in range(len(res)):
            x = min(abs(res[j][0]-lst1[i][0]),abs(lst1[i][0]-res[j][0]))
            y = min(abs(res[j][1]-lst1[i][1]),abs(lst1[i][1]-res[j][1]))
            loss = min(loss,lst1[i][2]*min(x,y))
        ret += loss
    return ret

#初回手動
ret = 0
res = made
for i in range(n):
    loss = 10**18
    for j in range(len(res)):
        x = min(abs(res[j][0]-lst1[i][0]),abs(lst1[i][0]-res[j][0]))
        y = min(abs(res[j][1]-lst1[i][1]),abs(lst1[i][1]-res[j][1]))
        loss = min(loss,lst1[i][2]*min(x,y))
    ret += loss
print(ret)

mura = 0
for i in range(n): #各路線について
    minloss = 10**24
    kouho = (0,0)
    for j in range(n): #各村について
        #x軸アプローチ
        res1 = funcx(j)
        #y軸アプローチ
        res2 = funcy(j)
        if res1<res2:
            if res1 < minloss:
                minloss = res1
                kouho = (lst1[j][0],0)
                mura = j
        else:
            if res2 < minloss:
                minloss = res2
                kouho = (0,lst1[j][1])
    made.append(kouho)
    print(minloss)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
#print(a)
tableud = [[0] * N for _ in range(N)]
tablelr = [[0] * N for _ in range(N)]
for i in range(N):
  x, y, _ = a[i]
  for j in range(N):
    tableud[i][j] = abs(a[j][0] - x) * a[j][2]
    tablelr[i][j] = abs(a[j][1] - y) * a[j][2]
zero = 0
for t in range(N):
  res = float("inf")
  if zero:
    print(0)
    continue
  for c in combi([x for x in range(N)], t):
    for i in range(1 << t):
      table = [10 ** 20] * N
      for j in range(N):
        table[j] = min(abs(a[j][0]), abs(a[j][1])) * a[j][2]
      for j in range(t):
        if i & (1 << j):
          for k in range(N):
            table[k] = min(table[k], tableud[c[j]][k])
        else:
          for k in range(N):
            table[k] = min(table[k], tablelr[c[j]][k])
      res = min(res, sum(table))
  print(res)
  if res == 0: zero = 1
res = float("inf")
for i in range(N):
  for j in range(N):
    if i == j: continue
    res = min(res, tablelr[i][j], tableud[i][j])
print(res)