Submission #1201844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201844		ofoz	Let's Win the Election (JOI22_ho_t3)	Pypy 3	27 / 100	775 ms	203132 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

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(l, r+1): res = min(res, f(mxCol))

# print(f(2))
print(res)

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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