oj.uz

Submission #756416

# Submission time Handle Problem Language Result Execution time Memory
756416 2023-06-11T16:53:33 Z iamjiamingliu Balloons (CEOI11_bal) Python 3
100 / 100
 1725 ms 49936 KB 
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3276 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3172 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3340 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3668 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 7116 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 13136 KB 50000 numbers
2 Correct 423 ms 15020 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 22696 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 947 ms 25676 KB 115362 numbers
2 Correct 1006 ms 31132 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1271 ms 33292 KB 154271 numbers
2 Correct 1725 ms 49696 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1566 ms 40172 KB 200000 numbers
2 Correct 1531 ms 49936 KB 199945 numbers