oj.uz

Submission #719728

# Submission time Handle Problem Language Result Execution time Memory
719728 2023-04-06T14:31:44 Z Boomyday Balloons (CEOI11_bal) PyPy 3
100 / 100
 886 ms 42508 KB 
from collections import deque

n = int(input())

x, r = [], []



def getrj(ri, xi, xj):
    return (xj-xi)/(4*ri)*(xj-xi)

assert (getrj(9, 0, 13)) - 4.694 <= 0.001


for i in range(n):
    xi, ri = map(int, input().split())
    x.append(xi)
    r.append(ri)






st = deque()
r2 = []

for bal in range(n):
    mn = r[bal]
    while st:
        tp = st.pop()
        mn = min(mn, getrj(r2[tp], x[tp], x[bal]))
        if mn >= r2[tp]:
            continue
        else:
            st.append(tp)
            break

    st.append(bal)




    print(mn)
    r2.append(mn)

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 18476 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 18488 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 19672 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 26880 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 27072 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 29852 KB 50000 numbers
2 Correct 296 ms 29476 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 34032 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 34768 KB 115362 numbers
2 Correct 531 ms 34428 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 36992 KB 154271 numbers
2 Correct 707 ms 42024 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 42508 KB 200000 numbers
2 Correct 789 ms 39620 KB 199945 numbers