1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Person:
def __init__(self, pos, walk_time, hear_distance):
self.pos = pos
self.walk_time = walk_time
self.hear_distance = hear_distance
def get_walk_time(self, c):
dist = abs(self.pos - c)
if dist <= self.hear_distance:
return 0
return (dist - self.hear_distance) * self.walk_time
def get_cost(people, c):
total_time = 0
for p in people:
total_time += p.get_walk_time(c)
return total_time
def bisection(people, left, right):
if left == right:
return left
mid = (left + right) // 2
if get_cost(people, mid) < get_cost(people, mid + 1):
return bisection(people, left, mid)
return bisection(people, mid + 1, right)
N = int(input())
people = []
for i in range(N):
P, W, D = tuple(map(int, input().split()))
people.append(Person(P, W, D))
people.sort(key=lambda x: x.pos)
print(get_cost(people, bisection(people, 0, people[-1].pos)))
|
