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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

def min_dis():
	cost = 0
	for X, Y, P in XYP:
		dis = []
		for nx in x:
			dis.append(abs(nx-X))
		for ny in y:
			dis.append(abs(ny-Y))
		cost += min(dis)*P
	return cost

def min_dis_add_x(i):
	cost = 0
	x_lis = x + [xx[i]]
	y_lis = y
	for X, Y, P in XYP:
		dis = []
		for nx in x_lis:
			dis.append(abs(nx-X))
		for ny in y_lis:
			dis.append(abs(ny-Y))
		cost += min(dis)*P
	return cost

def min_dis_add_y(i):
	cost = 0
	x_lis = x 
	y_lis = y + [yy[i]]
	for X, Y, P in XYP:
		dis = []
		for nx in x_lis:
			dis.append(abs(nx-X))
		for ny in y_lis:
			dis.append(abs(ny-Y))
		cost += min(dis)*P
	return cost

N = INT()
XYP = [LIST() for _ in range(N)]

xx = list(set([x[0] for x in XYP]))
yy = list(set([y[1] for y in XYP]))

n = len(xx)
m = len(yy)

x = [0]
y = [0]

#print("xx={}".format(xx))
#print("yy={}".format(yy))

print(min_dis())
for _ in range(N):
	#print(x, y)
	min_cost_x = INF
	idx = -1
	for i in range(n):
		if min_dis_add_x(i) < min_cost_x:
			min_cost_x = min_dis_add_x(i)
			idx = i
	min_cost_y = INF
	idy = -1
	for i in range(m):
		if min_dis_add_y(i) < min_cost_y:
			min_cost_y = min_dis_add_y(i)
			idy = i

	if min_cost_x <= min_cost_y:
		x.append(xx[idx])
		print(min_cost_x)
	else:
		y.append(yy[idy])
		print(min_cost_y)

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+1):
    ans = 10**11
    for rails in K_rails[i]:
        ans = min(ans, S(villages, rails))
    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]))
    #print(city)
    return min(xmin,ymin)*city[2]

import itertools

new=[0 for i in range(30)]


for q in range(n+1):
    #new=[[]]
    itr=itertools.combinations(range(n*2),q)
    #itr2=itertools.product([1,2],repeat=q)
    """
    for kumi in itr:
        for kumi2 in itr2:
            ta=[]
            c=0
            for num in kumi:
                if kumi2[c]==1:
                    ta.append(kumi[c])
                else:
                    ta.append(kumi[c]+n)              
                c+=1
            new.append(ta[:])
    """
               
    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:
#!/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.add(X[k])
            else:
                ny.add(Y[k - a])
        for ps in p:
            if ps[0] not in nx and ps[1] not in ny:
                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:
from copy import deepcopy
n = int(input())
data = []
x_candidate = []
y_candidate = []
for i in range(n):
    data.append(list(map(int, input().split())))
    x_candidate.append(data[i][0])
    y_candidate.append(data[i][1])
original = [10**6 for i in range(n)]
for i in range(n):
    original[i] = min(abs(data[i][0]), abs(data[i][1]))
for i in range(n+1):
    min_D = deepcopy(original)
    for p in range(i):
        best_line = (0, 0)
        best_dec = 0
        for x in x_candidate:
            sum_dec = 0
            for j in range(n):
                sum_dec += max(0, min_D[j] - abs(data[j][0] - x)) * data[j][2]
            if sum_dec > best_dec:
                best_dec = sum_dec
                best_line = (x, 0)
        for y in y_candidate:
            sum_dec = 0
            for j in range(n):
                sum_dec += max(0, min_D[j] - abs(data[j][1] - y)) * data[j][2]
            if sum_dec > best_dec:
                best_dec = sum_dec
                best_line = (0, y)
        for j in range(n):
            min_D[j] = min(min_D[j], abs(data[j][0] - best_line[0]), abs(data[j][1] - best_line[1]))
        #print(best_line)
    #print(min_D)
    ans = 0
    for j in range(n):
        ans += min_D[j] * data[j][2]
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
city = [[int(i) for i in input().split()] for _ in range(n)]
line_x = [0]
line_y = [0]

def calc(point, direction):
    ans = 0
    for x, y, p in city:
        dist = 0
        if direction == 'x':
            dist = abs(point - x) * p
        else:
            dist = abs(point - y) * p
        for xx in line_x:
            dist = min(dist, (abs(xx - x)) * p)
        for yy in line_y:
            dist = min(dist, (abs(yy - y)) * p)
        ans += dist
    return int(ans)

high = 10000
low = -10000
print(calc(0, 'x'))
for i in range(n):
    ans_list = []
    for direction in ['x', 'y']:
        while high - low > 1:
            mid_left = high/3+low*2/3
            mid_right = high*2/3+low/3
            if calc(mid_left, direction) == calc(mid_right, direction):
                low = mid_left
                high = mid_right
            elif calc(mid_left, direction) > calc(mid_right, direction):
                low = mid_left
            else:
                high = mid_right
        hh = high // 1
        ll = low // 1
        target = [ll - 2, ll - 1, ll, ll + 1]
        cand = ll + 2
        for t in target:
            if calc(t, direction) < calc(cand, direction):
                cand = t
        ans_list.append(cand)
    if calc(ans_list[0], 'x') < calc(ans_list[1], 'y'):
        print(calc(ans_list[0], 'x'))
        line_x.append((ans_list[0]))
    else:
        print(calc(ans_list[1], 'y'))
        line_y.append((ans_list[1]))

Submission status: Wrong Answer

Solution code:
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)


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


for f in range(2**n):
    kou = []
    for i in range(n):
        if (f>>i)&1 == 1:
            kou.append(i)
    num = len(kou)
    w = set(kou)
    if res[num] == 0:
        continue

    for rr in range(1<<num):
        yoko = set([10000])
        tate = set([10000])

        for i in range(num):
            if (rr>>i)&1 == 1:
                yoko.add(y[kou[i]])
            else:
                tate.add(x[kou[i]])

        tmp = 100
        """
        for i in range(n):
            if i in w:
                continue
            mi = 10**9
            for e in yoko:
                if mi > abs(e-y[i]):
                    mi = abs(e-y[i])
            for e in tate:
                if mi > abs(e-x[i]):
                    mi = abs(e-x[i])
            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:
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(streets):
    s = 0
    for v in village:
        min_dist = 100000
        for street in streets:
            if abs(v[0] - street[0]) < min_dist:
                min_dist = abs(v[0] - street[0])
            if abs(v[1] - street[1]) < min_dist:
                min_dist = abs(v[1] - street[1])
        # print(v, min_dist)
        s += v[2] * min_dist
    return s

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

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations, product
N = int(input())
T = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 9

for k in range(N + 1):
    ans = INF
    if k == 0:
        h_line, w_line = [0], [0]
        cost = [INF] * N
        for j, (h, w, p) in enumerate(T):
            for hl in h_line:
                cost[j] = min(cost[j], p * abs(hl - h))
            for wl in w_line:
                cost[j] = min(cost[j], p * abs(wl - w))
            ans = min(ans, sum(cost))
        print(ans)
        continue

    for targets in combinations(range(N), k):
        targets = list(targets)

        for pattern in product([0, 1], repeat=k):
            h_line, w_line = [0], [0]
            for i, p in enumerate(pattern):
                if p == 0:
                    h_line.append(T[targets[i]][0])
                else:
                    w_line.append(T[targets[i]][1])

            cost = [INF] * N
            for j, (h, w, p) in enumerate(T):
                for hl in h_line:
                    cost[j] = min(cost[j], p * abs(hl - h))
                for wl in w_line:
                    cost[j] = min(cost[j], p * abs(wl - w))
            ans = min(ans, sum(cost))

    print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    p = LIR(n)
    p.sort()
    m = 3**n
    s = 0
    for i,(x,y,num) in enumerate(p):
        d = min(abs(x),abs(y))
        s += num*d
        p[i].append(d)
    ans = [s]*(n+1)
    ans[-1] = 0
    for i in range(n):
        x,y,num,d = p[i]
        for j in range(i):
            nx,ny = p[j][:2]
            nd = min(abs(x-nx),abs(y-ny))
            if nd < d:
                d = nd
        ns = d*num
        if ns < s:
            s = ns
    ans[-2] = s
    for b in range(m):
        lx = []
        ly = []
        cnt = 0
        res = b
        for x,y,num,d in p:
            j = res%3
            if j:
                cnt += 1
                if j == 1:
                    lx.append(x)
                else:
                    ly.append(y)
            res //= 3
        if cnt+1 >= n:
            continue
        ly.sort()
        s = 0
        for x,y,num,d in p:
            i = bisect.bisect_left(lx,x)-1
            if i >= 0:
                nd = x-lx[i]
                if nd < d:
                    d = nd
            i += 1
            if i < len(lx):
                nd = lx[i]-x
                if nd < d:
                    d = nd
            i = bisect.bisect_left(ly,y)-1
            if i >= 0:
                nd = y-ly[i]
                if nd < d:
                    d = nd
            i += 1
            if i < len(ly):
                nd = ly[i]-y
                if nd < d:
                    d = nd
            s += d*num
        if s < ans[cnt]:
            ans[cnt] = s
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

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(streets):
    s = 0
    for v in village:
        min_dist = 100000
        for street in streets:
            if abs(v[0] - street[0]) < min_dist:
                min_dist = abs(v[0] - street[0])
            if abs(v[1] - street[1]) < min_dist:
                min_dist = abs(v[1] - street[1])
        # print(v, min_dist)
        s += v[2] * min_dist
    return s

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

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

Submission status: Wrong Answer

Solution code:
def population(n):
    if n == 0:
        return 0
    if n % 2 == 0:
        return population(n // 2)
    return 1 + population(n // 2)

N = int(input())
X = [0] * N
Y = [0] * N
P = [0] * N
for i in range(N):
    X[i], Y[i], P[i] = map(int, input().split())

ans = [10**10] * (N + 1)
for i in range(1 << (2 * N)):
    K = population(i)
    if K > N:
        continue
    cost = 0
    for j in range(N):
        if i & (1 << j) or i & (1 << (j + N)):
            continue
        cost2 = min(abs(X[j]), abs(Y[j]))
        for l in range(2 * N):
            if (i & (1 << l)) == 0:
                #print('cont', i)
                continue
            if l < N:
                #print('x')
                cost2 = min(cost2, abs(X[l] - X[j]))
            else:
                #print('y')
                cost2 = min(cost2, abs(Y[l - N] - Y[j]))
        cost += cost2 * P[j]
    ans[K] = min(ans[K], cost)
    #print(K, cost)
for i in range(N + 1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def ab(x):
    if x<0:
        return (-1)*x
    else:
        return x

n=int(input())
x=[]
y=[]
p=[]
for i in range(n):
    X,Y,P=map(int,input().split())
    x.append(X)
    y.append(Y)
    p.append(P)
rec=[0]*n
s=0
for i in range(n):
    rec[i]=min(ab(x[i]),ab(y[i]))*p[i]
    s+=rec[i]
print(s)
memory_x=[]
memory_y=[]
ans=float("inf")
ans_x=float("inf")
ans_y=float("inf")
for i in range(n):
    ans_x = ans
    ans_y = ans
    for j in range(-10000,10001):
        memo=0
        if not(j in memory_x):

            for k in range(n):
                if rec[k]>ab(x[k]-j)*p[k]:
                    memo+=ab(x[k]-j)*p[k]
                else:
                    memo+=rec[k]
            if memo<ans_x:
                ans_x=memo
                X=j
    for j in range(-10000,10001):
        memo = 0
        if not(j in memory_y):
            for k in range(n):
                if rec[k]>ab(y[k]-j)*p[k]:
                    memo+=ab(y[k]-j)*p[k]
                else:
                    memo+=rec[k]
            if memo<ans_y:
                ans_y=memo
                Y=j
    if ans_x>=ans_y:
        memory_y.append(Y)
        ans=ans_y
        for k in range(n):
            if rec[k] > ab(y[k] - Y) * p[k]:
                rec[k]= ab(y[k] - Y) * p[k]
    else:
        memory_x.append(X)
        ans = ans_x
        for k in range(n):
            if rec[k] > ab(x[k] - X) * p[k]:
                rec[k]= ab(x[k] - X) * p[k]
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
cities = []
for i in range(N):
    X,Y,P = map(int,input().split())
    cities.append([X,Y,P])
line = [float('inf')]*(N+1)
costs = []
for x,y,p in cities:
    costs.append(p*min(abs(x),abs(y)))
def func(D,V,K,costssum):
    queue = []
    if V == 0:
        K -= 1
    if V == 1:
        X = cities[D][0]
        for i in range(N):
            ncost = abs(cities[i][0]-X)*cities[i][2]
            if costs[i] > ncost:
                queue.append((i,costs[i]))
                costssum-=costs[i]-ncost
                costs[i] = ncost
    if V == 2:
        Y = cities[D][1]
        for i in range(N):
            ncost = abs(cities[i][1]-Y)*cities[i][2]
            if costs[i] > ncost:
                queue.append((i,costs[i]))
                costs[i] = ncost
    if D == N-1:
        line[K] = min(line[K],costssum)
        for i,cost in queue:
            costssum += cost-costs[i]
            costs[i] = cost
        return
    for i in range(3):
        func(D+1,i,K,costssum)
    for i,cost in queue:
        costssum += cost-costs[i]
        costs[i] = cost

for i in range(3):
    func(0,i,N,sum(costs))

for i in line:
    print(i)

Submission status: Wrong Answer

Solution code:
def ab(x):
    if x<0:
        return (-1)*x
    else:
        return x

n=int(input())
x=[]
y=[]
p=[]
for i in range(n):
    X,Y,P=map(int,input().split())
    x.append(X)
    y.append(Y)
    p.append(P)
rec=[0]*n
s=0
for i in range(n):
    rec[i]=min(ab(x[i]),ab(y[i]))*p[i]
    s+=rec[i]
print(s)
memory_x=[]
memory_y=[]
ans=float("inf")
ans_x=float("inf")
ans_y=float("inf")
for i in range(n):
    ans_x = ans
    ans_y = ans
    for j in range(-5,6):
        memo=0
        if not(j in memory_x):

            for k in range(n):
                if rec[k]>ab(x[k]-j)*p[k]:
                    memo+=ab(x[k]-j)*p[k]
                else:
                    memo+=rec[k]
            if memo<ans_x:
                ans_x=memo
                X=j
    for j in range(-5,6):
        memo = 0
        if not(j in memory_y):
            for k in range(n):
                if rec[k]>ab(y[k]-j)*p[k]:
                    memo+=ab(y[k]-j)*p[k]
                else:
                    memo+=rec[k]
            if memo<ans_y:
                ans_y=memo
                Y=j
    if ans_x>=ans_y:
        memory_y.append(Y)
        ans=ans_y
        for k in range(n):
            if rec[k] > ab(y[k] - Y) * p[k]:
                rec[k]= ab(y[k] - Y) * p[k]
    else:
        memory_x.append(X)
        ans = ans_x
        for k in range(n):
            if rec[k] > ab(x[k] - X) * p[k]:
                rec[k]= ab(x[k] - X) * p[k]
    print(ans)

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(streets):
    s = 0
    for v in village:
        min_dist = 100000
        for street in streets:
            if abs(v[0] - street[0]) < min_dist:
                min_dist = abs(v[0] - street[0])
            if abs(v[1] - street[1]) < min_dist:
                min_dist = abs(v[1] - street[1])
        # 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([(0,0)])
for k in range(N + 1):
    min_score = m
    for streets in itertools.combinations(candidate, k):
        # score
        s = score(streets)
        # print(streets, s)
        if s < min_score:
            min_score = s
    print(min_score)

Submission status: Wrong Answer

Solution code:
from itertools import product
import sys

input = sys.stdin.buffer.readline

n = int(input())
infi = 10 ** 10
kouho = []
for _ in range(n):
    x, y, p = map(int, input().split())
    cos = min(abs(x), abs(y)) * p
    kouho.append((cos, x, y, p))
kouho.sort(reverse=True)

kumiawase = list(product([0, 1], repeat=n))

ans = [infi] * (n + 1)


def calc(kouho, dele):
    res = infi
    num = len(dele)
    comb = list(product([0, 1], repeat=num))
    for kumi in comb:
        xroad = [0]
        yroad = [0]
        for i in range(num):
            idx = dele[i]
            _, x, y, p = kouho[idx]
            if kumi[i]:
                xroad.append(x)
            else:
                yroad.append(y)
        res1 = 0
        for i in range(n):
            temp = infi
            _, x, y, p = kouho[i]
            for xval in xroad:
                temp = min(temp, p * abs(xval - x))
            for yval in yroad:
                temp = min(temp, p * abs(y - yval))
            res1 += temp
        res = min(res1, res)
    return res


for kumi in kumiawase:
    for kumi in kumiawase:
        cnt = 0
        dele = []
        for i in range(n):
            if kumi[i]:
                cnt += 1
                dele.append(i)
        ans1 = calc(kouho, dele)
        if ans1 == 0:
            ans[cnt] = ans1
            for a in ans:
                print(a if a != infi else 0)
            exit()
        ans[cnt] = min(ans[cnt], calc(kouho, dele))

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

Submission status: Wrong Answer

Solution code:
import itertools

def f(xl,yl):
    ret=0
    for x,y,p in XYP:
        d=10**10
        for i in xl:
            d=min(d,abs(x-i))
            if d==0:
                break
        for i in yl:
            d=min(d,abs(y-i))
            if d==0:
                break
        ret+=d*p
    return ret

N=int(input())
XYP=[list(map(int,input().split())) for _ in range(N)]
mx=set()
my=set()
for x,y,p in XYP:
    if x!=0:
        mx.add(x)
    if y!=0:
        my.add(y)
mm=[]
for i in mx:
    mm.append((0,i))
for i in my:
    mm.append((1,i))
ln=(len(mm))
flg=False
s=10**10
for i in range(N+1):
    if flg or i==N:
        print(0)
    else:
        for l in itertools.permutations(mm,i):
            xi=[0]
            yi=[0]
            for fl,xy in l:
                if fl==0:
                    xi.append(xy)
                else:
                    yi.append(xy)
            s=min(s,f(xi,yi))
        if s==0:
            flg=True
        print(s)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 30
from itertools import combinations
N = int(input())
XYP = [list(map(int, input().split())) for _ in range(N)]
# X=0,Y=1
origin = [(0, 0), (1, 0)]

X = []
Y = []
all_points = []
for x, y, p in XYP:
    X.append((0,abs(x)))
    all_points.append((0,x))
    Y.append((1,abs(y)))
    all_points.append((1,y))

zerocnt = min(len(set(X)), len(set(Y)))

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+1-zerocnt):
    cost = INF
    for comb in combinations(all_points, 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:
import sys
input = sys.stdin.readline
def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)
def main():
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    ans = [float("inf")]*(n+1)
    for i in range(3 ** n):
        x = [0]
        y = [0]
        t = base10to(i,3)
        rail = 0
        if (len(t)<n):
            t = "0"*(n-len(t)) + t
        for j in range(n):
            if t[j]=="1":
                x.append(a[j][0])
                rail += 1
            elif t[j]=="2":
                y.append(a[j][1])
                rail += 1
        tnp = 0
        for j in range(n):
            mini = []
            for k in x:
                mini.append(abs(k-a[j][0]))
            for k in y:
                mini.append(abs(k-a[j][1]))
            tnp += a[j][2]*min(mini)
        ans[rail] = min(ans[rail], tnp)
    print(ans)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
n = int(input())
data = []
x_candidate = []
y_candidate = []
for i in range(n):
    data.append(list(map(int, input().split())))
    x_candidate.append(data[i][0])
    y_candidate.append(data[i][1])
original = [10**6 for i in range(n)]
for i in range(n):
    original[i] = min(abs(data[i][0]), abs(data[i][1]))
for i in range(n+1):
    min_D = deepcopy(original)
    for p in range(i):
        best_line = (0, 0)
        best_dec = 10**11
        for x in x_candidate:
            sum_dec = 0
            for j in range(n):
                sum_dec += min(abs(data[j][0] - x), min_D[j]) * data[j][2]
            if sum_dec < best_dec:
                best_dec = sum_dec
                best_line = (x, 0)
        for y in y_candidate:
            sum_dec = 0
            for j in range(n):
                sum_dec += min(abs(data[j][1] - y), min_D[j]) * data[j][2]
            if sum_dec < best_dec:
                best_dec = sum_dec
                best_line = (0, y)
        for j in range(n):
            min_D[j] = min(min_D[j], abs(data[j][0] - best_line[0]), abs(data[j][1] - best_line[1]))
        #print(best_line)
    ans = 0
    for j in range(n):
        ans += min_D[j] * data[j][2]
    print(ans)