Submission #756416

#	Time	Username	Problem	Language	Result	Execution time	Memory
756416		iamjiamingliu	Balloons (CEOI11_bal)	Cpython 3	100 / 100	1725 ms	49936 KiB

bal

import sys
input = sys.stdin.readline


from collections import namedtuple

Balloon = namedtuple('Balloon', ['x', 'radius'])
bounding_balloons = [Balloon(*map(int, input().split())) for _ in range(int(input()))]
prev_balloons = []


def max_possible_radius(prev: Balloon, new_x: int) -> int:
    return (new_x ** 2 + prev.x ** 2 - 2 * new_x * prev.x) / (4 * prev.radius)


all_radii = [0] * len(bounding_balloons)

for i, cur_balloon in enumerate(bounding_balloons):
    new_radius = cur_balloon.radius
    while prev_balloons:
        new_radius = min(new_radius, max_possible_radius(prev_balloons[-1], cur_balloon.x))
        if prev_balloons[-1].radius < new_radius:
            prev_balloons.pop()
        else:
            break
    all_radii[i] = new_radius
    prev_balloons.append(Balloon(cur_balloon.x, new_radius))

for r in all_radii:
    print(f'{r:.3f}')

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10