← 返回题目列表

AtCoder · m_solutions2020_e

E. M的解决方案

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

新的 AtCoder City 有无限的街道网格,如下:

  • 在城市的中心矗立着一座钟楼。 (0, 0) 是该点的坐标。
  • 一条笔直的街道,我们称之为 东西大街,东西走向并经过钟楼。 x- 二维坐标平面中的轴。
  • 还有无数条与东西大街平行的街道,距离为 1 他们之间。它们对应于线 二维坐标平面中的 \ldots, y = -2, y = -1, y = 1, y = 2, \ldots 。
  • 一条笔直的街道,我们称之为 南北大街,南北走向,经过钟楼。 y- 二维坐标平面中的轴。
  • 还有无数条与南北大街平行的街道,距离为 1 他们之间。它们对应于线 二维坐标平面中的 \ldots, x = -2, x = -1, x = 1, x = 2, \ldots 。

有 N AtCoder 新城住宅区。 i第一个区域位于与坐标的交点处 (X_i, Y_i) 人口为 P_i。城市中的每个公民都居住在这些区域之一。

该市目前只有两条铁路,无限延伸,一条沿东西大街,另一条沿南北大街。
市长M-kun认为这些对于通勤者来说不够,所以他决定选择 K 街道并沿着每条街道建造一条无限延伸的铁路。

让 步行距离 每个公民的 是他/她的居住区到最近的铁路的距离。
M君想要修建铁路,以便所有公民的步行距离总和, S被最小化。

对于每个 K = 0, 1, 2, \dots, N,最小可能值是多少 S 修建铁路后?

约束

  • 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
  • 的位置 N 住宅区, (X_i, Y_i),都是不同的。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
X_1 Y_1 P_1
X_2 Y_2 P_2
 :  :  :
X_N Y_N P_N

输出

打印答案 N+1 行。
的 树的 i第行 (i = 1, \ldots, N+1) 应包含最小可能值 S 为该案修建铁路后 K = i-1.


示例输入 1

3
1 2 300
3 3 600
1 4 800

示例输出 1

2900
900
0
0

当 K = 0, 辖区居民 1, 2,和 3 必须步行的距离 1, 3,和 1分别到达铁路。
因此,所有公民的步行距离总和, S是 1 \times 300 + 3 \times 600 + 1 \times 800 = 2900.

当 K = 1,如果我们沿着该线对应的街道修建一条铁路 y = 4 在坐标平面上,区域居民的步行距离 1, 2,和 3 成为 1, 1,和 0。
然后, S = 1 \times 300 + 1 \times 600 + 0 \times 800 = 900.
对于修建铁路的地点,我们有许多其他选择,但没有一个能够使 S 小于 900.

当 K = 2,如果我们沿着对应线路的街道修建一条铁路 x = 1 和 x = 3 在坐标平面上,所有公民步行距离可达一条铁路 0,所以 S = 0。我们还可以有 S = 0 当 K = 3.

下图展示了该案例中修建铁路的最佳方式 K = 0, 1, 2.
涂成蓝色的街道代表我们修建铁路的道路。


示例输入 2

5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400

示例输出 2

13800
1600
0
0
0
0

下图展示了该案例中修建铁路的最佳方式 K = 1, 2.


示例输入 3

6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200

示例输出 3

26700
13900
3200
1200
0
0
0

下图展示了该案例的最佳铁路建设方式 K = 3.


示例输入 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

示例输出 4

2576709
1569381
868031
605676
366338
141903
0
0
0

下图展示了该案例的最佳铁路建设方式 K = 4.