Submission #1201160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201160		ofoz	Let's Win the Election (JOI22_ho_t3)	Pypy 3	11 / 100	867 ms	202396 KiB

Main

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

memo = [[-1] * (n+1) for _ in range(n+1)]
def dp(i: int, col: int, mxCol: int, memo: list[list[int]]):
    if i == -1 and col == 0: return 0
    
    if i < 0 or col < 0: return float('inf')
    # print(i, col, memo[i][col])
    if memo[i][col] != -1: return memo[i][col]
    x = float('inf')
    if col: x = dp(i-1, col-1, mxCol, memo) + (end[i]/col)
    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(n-1, col, 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
res = float('inf')
for i in range(l, r+1): res = min(res, f(i))
print(res)
# let dp[i][col][k] be the minimum amount of time to get col collaborators with k voters up to the i-th point.
# dp[i][col][k] = min(
#                dp[i-1][col-1][k-1] + b_i/(col+1),
#                dp[i-1][col][k-1] + a_i/(mxCol+1),
#                dp[i-1][col][k],
# )
# dp[i][0][0] = 0 for all i

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 44%)

=======

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23