Submission #1201122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201122		ofoz	Let's Win the Election (JOI22_ho_t3)	Pypy 3	23 / 100	2606 ms	1114112 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)] for _ in range(n+1)]
def dp(i: int, col: int, k: int, mxCol: int):
    if col == 0 and k == 0: return 0
    if col > k or i < 0 or col < 0: return float('inf')
    if memo[i][col][k] != -1: return memo[i][col][k]

    x = float('inf')
    if col: x = dp(i-1, col-1, k-1, mxCol) + (end[i]/col)
    y = dp(i-1, col, k-1, mxCol) + (start[i]/(mxCol+1))
    z = dp(i-1, col, k, mxCol)
    memo[i][col][k] = min(x, y, z)

    return memo[i][col][k]

res = float('inf')
for col in range(n):
    res = min(res, dp(n-1, col, k, col))
    memo = [[[-1] * (n+1) for _ in range(n+1)] for _ in range(n+1)]

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 52%)

=======

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