Submission #1200903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200903		ofoz	Let's Win the Election (JOI22_ho_t3)	Pypy 3	10 / 100	160 ms	51588 KiB

Main

n = int(input())
k = int(input())
s = []
e = []
for i in range(n):
    a, b = map(int, input().split(" "))
    s.append((a, b, i))
    if b != -1: e.append((b, i))
s.sort()
s.reverse()
e.sort()
e.reverse()



res = float('inf')
for t in range(1, n+1):
    seg = s.copy()
    end = e.copy()
    time = cur = 0
    c = 1   
    voted = [0] * n

    while end and (c < t):
        b, i = end.pop()
        voted[i] = 1
        time += (b/c)

        cur += 1
        c += 1
    
    if c < t:
        break

    while seg and cur < k:
        a, b, i = seg.pop()
        if voted[i]: continue
        voted[i] = 1
        time += a/c
        cur += 1


    res = min(res, time)

print(res)

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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