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 itertools

N = int(input())
XYP = [list(map(int, input().split())) for i in range(N)]
x_min = min(x for x, _, _ in XYP)
x_max = max(x for x, _, _ in XYP)
y_min = min(y for _, y, _ in XYP)
y_max = max(y for _, y, _ in XYP)

print(x_min, x_max, y_min, y_max)

Lines = {(0, None), (None, 0)}
c_lines = {(x, None) for x in range(x_min, x_max + 1)} \
    | {(None, y) for y in range(y_min, y_max + 1)} \
    - Lines


def calc_distance(xyp, line):
    lx, ly = line
    x, y, p = xyp
    if lx is None:
        return abs(y - ly) * p
    if ly is None:
        return abs(x - lx) * p
    return min(abs(x - lx), abs(y - ly)) * p


def calc_s(lines):
    d = []
    for xyp in XYP:
        d.append(min(calc_distance(xyp, line) for line in lines))
    return sum(d)


zero = False
for k in range(N + 1):
    if zero:
        print(0)
        continue
    s = []
    for item in itertools.combinations(c_lines, k):
        t_lines = set(item) | Lines
        s.append(calc_s(t_lines))
    print(min(s))
    if min(s) == 0:
        zero = True

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for _ in range(n):
  a.append(list(map(int,input().split())))
ans=sum([min(abs(a[i][0]),abs(a[i][1]))*a[i][2] for i in range(n)])
print(ans)
a.sort(key=lambda x:x[2],reverse=True)
for j in range(n):
  print(min(sum([min(min([abs(a[i][0]-a[k][0]) for k in range(j+1)]),abs(a[i][0]),abs(a[i][1]))*a[i][2] for i in range(n)]),sum([min(min([abs(a[i][1]-a[k][1]) for k in range(j+1)]),abs(a[i][1]),abs(a[i][0]))*a[i][2] for i in range(n)])))

Submission status: Wrong Answer

Solution code:
def hersCode(n, f):
  l = 10001
  r = -10000
  for i in range(N):
    if (1 << i) & n:
      x, y, p = XYP[i]
      if f:
        l = min(l, x)
        r = max(r, x)
      else:
        l = min(l, y)
        r = max(r, y)
  r += 1

  while abs(l - r) > 2:
    d1 = l + (r - l) // 3
    d2 = r - (r - l) // 3
    dd1 = exe(n, f, d1)
    dd2 = exe(n, f, d2)
    if dd1 > dd2:
      r = d2
    else:
      l = d1
  ans = 0
  for i in range(l, r):
    ans = max(ans, exe(n, f, i))
  return ans

def exe(n, f, m):
  q = 0
  for i in range(N):
    if (1 << i) & n:
      x, y, p = XYP[i]
      if f == True:
        if min(abs(x), abs(y)) > abs(x - m):
          q += L[i] - abs(x - m) * p
      else:
        if min(abs(x), abs(y)) > abs(y - m):
          q += L[i] - abs(y - m) * p
  return q

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

if N == 1:
  x, y, p = XYP[0]
  print(min(abs(x), abs(y)) * p)
  print(0)
  exit()

L = [0] * N
c = 0
t = 0
for x, y, p in XYP:
  t += min(abs(x), abs(y)) * p
  L[c] = min(abs(x), abs(y)) * p
  c += 1

D = [0] * (1 << N)

for i in range(1, 1 << N):
  D[i] = max(hersCode(i, True), hersCode(i, False))

DP = [[0] * (1 << N) for _ in range(N)]

for i in range(1 << N):
  DP[1][i] = D[i]

exit()
for i in range(2, N):
  for n in range(1, i):
    for j in range(1 << N):
      for k in range(1 << N):
        if ~j & k: continue
        if j == k: continue
        d = j ^ k
        DP[i][j] = max(DP[i][j], DP[n][k] + DP[i - n][d])

for i in range(N):
  print(t - max(DP[i]))
print(0)

Submission status: Wrong Answer

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

    x_cost_dict = {}
    y_cost_dict = {}
    for i in xyp:
        if i[0] in x_cost_dict.keys():
            x_cost_dict[i[0]] += i[2]
        else:
            x_cost_dict[i[0]] = i[2]

        if i[1] in y_cost_dict.keys():
            y_cost_dict[i[1]] += i[2]
        else:
            y_cost_dict[i[1]] = i[2]

    print(sum([min(i[0], i[1]) * i[2] for i in xyp]))

    train_list = []
    cost = -1
    for key in x_cost_dict:
        tmp_cost = sum(
            [min(abs(j[0]), abs(j[1]), abs(j[0] - key)) * j[2] for j in xyp])
        if tmp_cost < cost or cost < 0:
            cost = tmp_cost
            train = [key, 0]
    for key in y_cost_dict:
        tmp_cost = sum(
            [min(abs(j[0]), abs(j[1]), abs(j[1] - key)) * j[2] for j in xyp])
        if tmp_cost < cost or cost < 0:
            cost = tmp_cost
            train = [0, key]
    train_list.append(train)
    print(cost)

    for i in range(1, n):
        cost = -1
        for key in x_cost_dict:
            tmp_cost = sum([min(abs(j[0]), abs(j[1]), abs(j[0] - key), min([min(abs(j[0] - k[0]), abs(j[1] - k[1])) for k in train_list])) * j[2] for j in xyp])
            if tmp_cost < cost or cost < 0:
                cost = tmp_cost
                train = [key, 0]
        for key in y_cost_dict:
            tmp_cost = sum([min(abs(j[0]), abs(j[1]), abs(j[1] - key), min([min(abs(j[0] - k[0]), abs(j[1] - k[1])) for k in train_list])) * j[2] for j in xyp])
            if tmp_cost < cost or cost < 0:
                cost = tmp_cost
                train = [0, key]

        train_list.append(train)
        print(cost)

Submission status: Wrong Answer

Solution code:
from itertools import combinations as comb
n = int(input())
ts = [list(map(int, input().split())) for _ in range(n)]
res = 0
for i in ts:
    tmp = min(abs(i[0]),abs(i[1]))
    res += tmp * i[2]
print(res)

bars = {}
for i in ts:
    tmp = min(abs(i[0]),abs(i[1]))
    if "x:"+str(i[0]) not in bars:
        bars["x:"+str(i[0])] = 1
    if "y:"+str(i[1]) not in bars:
        bars["y:"+str(i[1])] = 1
for k in range(1,n+1):
    res = float('inf')
    for this_bars in comb(bars,k):
        this_bars = ["x:0"] + ["y:0"] + list(this_bars)
        ts_tmp = [float('inf')]*n
        for this_bars in this_bars:
            for t in range(n):
                if this_bars[0] == 'x':
                    ts_tmp[t] =  min(ts_tmp[t], abs(ts[t][0] - int(this_bars[2:])) * ts[t][2])
                else:
                    ts_tmp[t] = min(ts_tmp[t], abs(ts[t][1] - int(this_bars[2:])) * ts[t][2])

        res = min(res, sum(ts_tmp))
    print(res)

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 = 0
            kakuy = i[1]
    if s != shoki:
        koshin(kakux,kakuy)
    s = shoki
    print(s)

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from itertools import combinations
from collections import defaultdict

def main():
	n=II()
	dx=[defaultdict(lambda:-1) for _ in range(n)]
	dy=[defaultdict(lambda:-1) for _ in range(n)]
	X=[]
	Y=[]
	P=[]
	for _ in range(n):
		x,y,p=MI()
		X.append(x)
		Y.append(y)
		P.append(p)
	#print(X,Y,P)

	for i in range(n):
		aans=10**15
		a=combinations(range(n),i)
		for li in list(a):
			#print(li)
			for j in range(1<<i):
				x=[0]
				y=[0]
				for k in range(i):
					if j&1<<k:
						x.append(X[li[k]])
					else:
						y.append(Y[li[k]])
				#print(i,j,k)
				#print(x,y)
				x=tuple(x)
				y=tuple(y)

				ans=0
				for ii in range(n):
					if dx[ii][x]!=-1:
						dxx=dx[ii][x]
					else:
						dxx=10**6
						for xx in x:
							dxx=min(dxx,abs(X[ii]-xx))
						dx[ii][x]=dxx
					if dy[ii][y]!=-1:
						dyy=dy[ii][y]
					else:
						dyy=10**6
						for yy in y:
							dyy=min(dyy,abs(Y[ii]-yy))
						dy[ii][y]=dyy

					ans+=P[ii]*min(dxx,dyy)
			aans=min(aans,ans)
		print(aans)
	print(0)













































if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())
town = [list(map(int, input().split(' '))) for i in range(N)]
closed = [[0, 0] for i in range(N)]
S = [0]
X = set()
Y = set()
zero = max(N,2*N-len(X)-len(Y))
for x, y, p in town:
    X.add(x)
    Y.add(y)
    S[0] += p * min(abs(x), abs(y))
for i in range(1, N):
    tmp = S[i - 1]
    x = False
    y = False
    for j in X:
        tmp_x = sum(
            [town[i][-1] * min(min(abs(town[i][0] - closed[i][0]), abs(town[i][0] - j)), abs(town[i][1] - closed[i][1]))
             for i in range(N)])
        if tmp_x < tmp:
            x = j
            tmp = tmp_x
    for j in Y:
        tmp_y = sum(
            [town[i][-1] * min(min(abs(town[i][1] - closed[i][1]), abs(town[i][1] - j)), abs(closed[i][0] - town[i][0]))
             for i in range(N)])
        if tmp_y < tmp:
            tmp = tmp_y
            y = j
    S.append(tmp)
    if y:
        for i in range(N):
            if abs(closed[i][1] - town[i][1]) > abs(y - town[i][1]):
                closed[i][1] = y
    else:
        for i in range(N):
            if abs(closed[i][0] - town[i][0]) > abs(x - town[i][0]):
                closed[i][0] = x
S.append(0)
for i in S:
    print(i)

Submission status: Wrong Answer

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

    x_cost_dict = {}
    y_cost_dict = {}
    for i in xyp:
        if i[0] in x_cost_dict.keys():
            x_cost_dict[i[0]] += i[2]
        else:
            x_cost_dict[i[0]] = i[2]

        if i[1] in y_cost_dict.keys():
            y_cost_dict[i[1]] += i[2]
        else:
            y_cost_dict[i[1]] = i[2]

    print(sum([min(i[0], i[1]) * i[2] for i in xyp]))

    train_list = []
    cost = -1
    for key in x_cost_dict:
        tmp_cost = sum(
            [min(abs(j[0]), abs(j[1]), abs(j[0] - key)) * j[2] for j in xyp])
        if tmp_cost < cost or cost < 0:
            cost = tmp_cost
            train = [key, 0]
    for key in y_cost_dict:
        tmp_cost = sum(
            [min(abs(j[0]), abs(j[1]), abs(j[1] - key)) * j[2] for j in xyp])
        if tmp_cost < cost or cost < 0:
            cost = tmp_cost
            train = [0, key]
    train_list.append(train)
    print(cost)

    for i in range(1, n):
        cost = -1
        for key in x_cost_dict:
            tmp_cost = sum([min(abs(j[0]), abs(j[1]), abs(j[0] - key), min([min(abs(j[0] - k[0]), abs(j[1] - k[1])) for k in train_list])) * j[2] for j in xyp])
            if tmp_cost < cost or cost < 0:
                cost = tmp_cost
                train = [key, 0]
        for key in y_cost_dict:
            tmp_cost = sum([min(abs(j[0]), abs(j[1]), abs(j[1] - key), min([min(abs(j[0] - k[0]), abs(j[1] - k[1])) for k in train_list])) * j[2] for j in xyp])
            if tmp_cost < cost or cost < 0:
                cost = tmp_cost
                train = [key, 0]

        train_list.append(train)
        print(cost)

Submission status: Wrong Answer

Solution code:
N = int(input())
town = [list(map(int, input().split(' '))) for i in range(N)]
closed = [[0, 0] for i in range(N)]
S = [0]
X = set()
Y = set()
zero = max(N,2*N-len(X)-len(Y))
for x, y, p in town:
    X.add(x)
    Y.add(y)
    S[0] += p * min(abs(x), abs(y))
for i in range(1, N):
    tmp = S[i - 1]
    x = False
    y = False
    for j in X:
        tmp_x = sum(
            [town[i][-1] * min(min(abs(town[i][0] - closed[i][0]), abs(town[i][0] - j)), abs(town[i][1] - closed[i][1]))
             for i in range(N)])
        if tmp_x < tmp:
            x = j
            tmp = tmp_x
    for j in Y:
        tmp_y = sum(
            [town[i][-1] * min(min(abs(town[i][1] - closed[i][1]), abs(town[i][1] - j)), abs(closed[i][0] - town[i][0]))
             for i in range(N)])
        if tmp_y < tmp:
            tmp = tmp_y
            y = j
    S.append(tmp)
    if y:
        for i in range(N):
            if abs(closed[i][1] - town[i][1]) > abs(y - town[i][1]):
                closed[i][1] = y
    else:
        for i in range(N):
            if abs(closed[i][0] - town[i][0]) > abs(x - town[i][0]):
                closed[i][0] = x
S.append(0)
for i in S:
    print(i)
print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[None]*n
y=[None]*n
p=[None]*n
distance=0
lines=[0]*n
linesx=[0]*n
linesy=[0]*n
linestotal=[0]*n
for i in range(n):
  x[i],y[i],p[i]=list(map(int,input().split()))
for j in range(n):
    lines[j]=min(abs(x[j]),abs(y[j]))*p[j]
    distance+=lines[j]
print(distance)
for i in range(n-1):
  tempx=0
  tempy=0
  for k in range(i-1):
    tx=abs(x[i]-x[k])*p[i]
    ty=abs(y[i]-y[k])*p[i]
    if tx<lines[k]:
      tempx+=lines[k]-tx
    if ty<lines[k]:
      tempy+=lines[k]-ty
  for j in range(i+1,n):
    tempx+=abs(x[i]-x[j])*p[i]
    tempy+=abs(y[i]-y[j])*p[i]
    #print(j)
    if x[i]==x[j]:
      linesx[i]+=lines[j]
      linesx[j]+=lines[i]
    if y[i]==y[j]:
      linesy[i]+=lines[j]
      linesy[j]+=lines[i]
    linesx[i]+=tempx
    linesy[i]+=tempy
for i in range(n):
  linestotal[i]=max(linesx[i],linesy[i])

#print(linesx)
#print(linesy)
linestotal.sort(reverse=True)     
for i in range(n):
  if distance>linestotal[i]:
    distance-=linestotal[i]
  else:
    distance=0
  print(distance)

Submission status: Wrong Answer

Solution code:
N = int(input())
town = [list(map(int, input().split(' '))) for i in range(N)]
closed = [[0, 0] for i in range(N)]
print(closed)
S = [0]
X = set()
Y = set()
zero = max(N,2*N-len(X)-len(Y))
for x, y, p in town:
    X.add(x)
    Y.add(y)
    S[0] += p * min(abs(x), abs(y))
for i in range(1, N):
    tmp = S[i - 1]
    x = False
    y = False
    for j in X:
        tmp_x = sum(
            [town[i][-1] * min(min(abs(town[i][0] - closed[i][0]), abs(town[i][0] - j)), abs(town[i][1] - closed[i][1]))
             for i in range(N)])
        if tmp_x < tmp:
            x = j
            tmp = tmp_x
    for j in Y:
        tmp_y = sum(
            [town[i][-1] * min(min(abs(town[i][1] - closed[i][1]), abs(town[i][1] - j)), abs(closed[i][0] - town[i][0]))
             for i in range(N)])
        if tmp_y < tmp:
            tmp = tmp_y
            y = j
    S.append(tmp)
    if y:
        for i in range(N):
            if abs(closed[i][1] - town[i][1]) > abs(y - town[i][1]):
                closed[i][1] = y
    else:
        for i in range(N):
            if abs(closed[i][0] - town[i][0]) > abs(x - town[i][0]):
                closed[i][0] = x
    print(closed)
S.append(0)
for i in S:
    print(i)
print(0)

Submission status: Wrong Answer

Solution code:
import itertools

N=int(input())

X=list()
Y=list()
P=list()

Xset=set()
Yset=set()
for i in range(N):
    x,y,p=list(map(int,input().split()))
    X.append(x)
    Y.append(y)
    P.append(p)

    Xset.add("X"+str(x))
    Yset.add("Y"+str(y))

XsetList=list(Xset)
Xn=len(XsetList)
YsetList=list(Yset)
Yn=len(YsetList)

Z=XsetList+YsetList

def calcS(nlines, linespec):
    # print(linespec)

    xlines=[0]
    ylines=[0]

    if nlines>0:
        for line in linespec:
            # print(line)
            if line[0]=="X":
                xlines.append(int(line[1:]))
            else:
                ylines.append(int(line[1:]))

    # print(xlines)
    # print(ylines)

    S=0
    for i in range(N):
        cx = 1000000*10000
        cy = 1000000*10000
        for xi in xlines:
            cx = min(cx, abs(xi-X[i])*P[i])
        for yi in ylines:
            cy = min(cy, abs(yi-Y[i])*P[i])
        if cx < cy:
            S+=cx
        else:
            S+=cy
    return S

S = 15*1000000*10000
S=min(S,calcS(0, None))
print(S)

for k in range(1,N+1):
    L=itertools.combinations(Z,k)
    S = 15*1000000*10000
    for ll in L:
        # print(ll)
        S=min(S,calcS(k, ll))
    print(S)

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def is_ok(arg):
    s = 0
    t = 0
    if arg in dx:
        return 0
    else:
        for j in range(n):
            s += min(a[i-1][j], p[j]*abs(x[j]-arg))
            t += min(a[i-1][j], p[j]*abs(x[j]-(arg+1)))
        reg_x = s
        return s <= t

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

def is_ok2(arg):
    s = 0
    t = 0 
    if arg in dy:
        return 0
    else:
        for j in range(n):
            s += min(a[i-1][j], p[j]*abs(x[j]-arg))
            t += min(a[i-1][j], p[j]*abs(y[j]-(arg+1)))
        reg_y = s
        return s <= t

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


n = INT()
x = [0]*n
y = [0]*n
p = [0]*n
for i in range(n):
    x[i], y[i], p[i] = MAP()

a = [[inf]*(n) for i in range(n+1)]
# a[i][j]: i本目の道を建設した時の、集落jの歩行距離の合計値
dx = [0]
dy = [0]
reg_x = inf
reg_y = inf
for j in range(n):
    a[0][j] = p[j]*min(abs(x[j]), abs(y[j]))
    print(sum(a[0][:]))

for i in range(1,n+1):
    tmp_x = meguru_bisect(-10001,10001)
    tmp_y = meguru_bisect2(-10001,10001)
    if reg_x < reg_y:
        dx.append(tmp_x)
        for j in range(n):
            a[i][j] = min(a[i-1][j], p[j]*abs(x[j]-tmp_x))
    else:
        dy.append(tmp_y)
        for j in range(n):
            a[i][j] = min(a[i-1][j], p[j]*abs(y[j]-tmp_y))
    print(sum(a[i][:]))

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
town = []
for i in range(N):
  X, Y, P = [int(i) for i in input().split()]
  if X != 0 and Y != 0:
    town.append([X, Y, P])

for k in range(N+1):
  x = [(t[0], 'x') for t in town]
  y = [(t[1], 'y') for t in town]
  comb = list(itertools.combinations(x + y, k))
  min_cost = 20000 * 15 * 1000000
  for c in comb:
    c = list(c)
    c.append((0, 'x'))
    c.append((0, 'y'))
    cost = 0
    for x, y, p in town:
      min_dist = 10*+6
      for rail in c:
        if rail[1] == 'x':
          min_dist = min(min_dist, abs(x-rail[0]))
        else:
          min_dist = min(min_dist, abs(y-rail[0]))
      cost += min_dist * p
    min_cost = min(min_cost, cost)
  print(min_cost)

Submission status: Wrong Answer

Solution code:

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

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

    print(S)

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

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

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

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

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

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

    ans = [S]*N

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


main()

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())

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

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

mincostls = [0 for _ in range(n)]

for i in range(n):
    mincostls[i] = min(abs(xyp[i][0]), abs(xyp[i][1])) * xyp[i][2]

sumcost = sum(mincostls)

print(sumcost)

for i in range(1, n+1):
    if sumcost != 0:
        presentmincostls = copy.deepcopy(mincostls)
        presentsumcost = sum(presentmincostls)
        for j in range(n):
            tmpx = xyp[j][0]
            tmpcostsum = 0
            tmpmincostls = [0 for _ in range(n)]
            for k in range(n):
                tmpmincostls[k] = min(abs(xyp[k][0] - tmpx) * xyp[k][2], mincostls[k])
                tmpcostsum += min(abs(xyp[k][0] - tmpx) * xyp[k][2], mincostls[k])
            if tmpcostsum < presentsumcost:
                presentsumcost = tmpcostsum
                presentmincostls = copy.deepcopy(tmpmincostls)
            
            tmpy = xyp[j][1]
            tmpcostsum = 0
            tmpmincostls = [0 for _ in range(n)]
            for k in range(n):
                tmpmincostls[k] = min(abs(xyp[k][1] - tmpy) * xyp[k][2], mincostls[k])
                tmpcostsum += min(abs(xyp[k][1] - tmpy) * xyp[k][2], mincostls[k])
            if tmpcostsum < presentsumcost:
                presentsumcost = tmpcostsum
                presentmincostls = copy.deepcopy(tmpmincostls)
        mincostls = copy.deepcopy(presentmincostls)
        print(presentsumcost)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
from itertools import product
from bisect import bisect_left


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



def solve(N, XYP, INF=1<<61):
    # 3^N通り全て試す
    # 東西、左右、道なしの3通り
    minK = [INF for i in range(N+1)]
    score = 0
    for x, y, p in XYP:
        score += min(abs(x), abs(y)) * p
    minK[0] = score

    for ptn in product(range(3), repeat=N):
        nh = ptn.count(1)
        nv = ptn.count(2)
        k = nh + nv
        # calculate score
        score = 0
        nearest_x = [abs(x)*p for x, y, p in XYP]
        nearest_y = [abs(y)*p for x, y, p in XYP]
        for i in range(N):
            for j in range(N):
                if ptn[j] == 1:
                    nearest_x[i] = min(nearest_x[i], abs(x - XYP[j][0])*p)
                elif ptn[j] == 2:
                    nearest_y[i] = min(nearest_y[i], abs(y - XYP[j][1])*p)
                
        for i in range(N):
            score += min(nearest_x[i], nearest_y[i])
        minK[k] = min(minK[k], score)
    
    for k in range(0, N+1):
        print(minK[k])
    


if __name__ == '__main__':
    inputs = read()
    solve(*inputs)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
def main():
    def search(k):
        MIN = float('inf')
        for cx in range(k + 1):
            cy = k - cx
            for LX in combinations(xset, cx):
                for LY in combinations(yset, cy):
                    if len(LX) == 0:
                        MIN = min(MIN, sum(p * min(abs(x), min(abs(y - ly) for ly in LY)) for (x, y), p in zip(X, P)))
                    elif len(LY) == 0:
                        MIN = min(MIN, sum(p * min(min(abs(x - lx) for lx in LX), abs(y)) for (x, y), p in zip(X, P)))
                    else:
                        MIN = min(MIN, sum(p * min(min(abs(x - lx) for lx in LX), min(abs(y - ly) for ly in LY)) for (x, y), p in zip(X, P)))
        return MIN


    n = int(input())
    X, P, M = [], [], []
    xset, yset = set(), set()
    for _ in range(n):
        x, y, p = map(int, input().split())
        if x != 0 and y != 0:
            X.append([x, y])
            P.append(p)
            M.append(min(abs(x), abs(y)))
            xset.add(x)
            yset.add(y)
    LIM = min(len(xset), len(yset))
    ans = sum(m * p for m, p in zip(M, P))
    print(ans)
    for k in range(1, n + 1):
        if k >= LIM:
            print(0)
        else:
            print(search(k))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
XYP = [[int(x) for x in input().split()] for _ in range(N)]

a0 = 0
for i in range(N):
    a0 += min(XYP[i][0], XYP[i][1]) * XYP[i][2]

ans = [a0] * (N+1)

for i in range(3**N):
    tmp = i
    X = [0]
    Y = [0]
    c = 0
    for j in range(N):
        if(tmp % 3 == 1):
            X.append(XYP[j][0])
            c += 1
        elif(tmp %3 == 2):
            Y.append(XYP[j][1])
            c += 1
        tmp //= 3
    
    a = 0
    for j in range(N):
        dx = min([abs(x - XYP[j][0]) for x in X])
        dy = min([abs(y - XYP[j][1]) for y in Y])
        a += XYP[j][2] * min(dx,dy)
    
    if(ans[c] > a):
        ans[c] = a

for a in ans:
    print(a)