n = int(input())
k = int(input())
start = [0] * n
end = [0] * n
pairs = []
for i in range(n):
a, b = map(int, input().split(" "))
if b == -1: b = float('inf')
pairs.append((a, b))
pairs = sorted(pairs, key = lambda p: (p[1], -p[0]))
for i, (a, b) in enumerate(pairs):
start[i] = a
end[i] = b
sm = [[0] * (n+1) for _ in range(n+1)] # sm[i][c] -> minimum sum obtained by adding up c elements of index higher than i
for i in range(n-1, -1, -1):
for c in range(1, n+1):
if not c: continue
if (n - i) < c:
sm[i][c] = float('inf')
continue
if i == n-1: sm[i][c] = start[i]
else: sm[i][c] = min(sm[i+1][c-1] + start[i], sm[i+1][c])
def dp(i: int, col: int, mxCol: int, memo: list[list[list[int]]]):
global sm
if col == mxCol: return float(sm[i][k-i])/(mxCol+1)
if i == n: return float('inf')
if memo[i][col] != -1: return memo[i][col]
x = dp(i+1, col+1, mxCol, memo) + (end[i]/(col+1))
y = dp(i+1, col, mxCol, memo) + (start[i]/(mxCol+1))
memo[i][col] = min(x, y)
return memo[i][col]
def f(col: int):
memo = [[-1] * (n+1) for _ in range(n+1)]
return dp(0, 0, col, memo)
res = float('inf')
"""
l = 0
r = n
while r-l>2:
m1 = l + (r-l)//3
m2 = r - (r-l)//3
f1 = f(m1)
f2 = f(m2)
if f1 > f2: l = m1
else: r = m2
"""
for mxCol in range(n+1): res = min(res, f(mxCol))
# print(f(2))
print(res)
Compilation message (stdout)
Compiling 'Main.py'...
=======
adding: __main__.pyc (deflated 44%)
=======
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |