Submission #1230526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230526		ackerman2840	Palembang Bridges (APIO15_bridge)	Pypy 3	100 / 100	684 ms	86028 KiB

bridge

from heapq import heappush, heappop

def cmp(a):
    return a[0] + a[1]

lpq = []  # max-heap using negatives
rpq = []  # min-heap
lsum = 0
rsum = 0

def insert(x):
    global lsum, rsum
    median = -lpq[0] if lpq else 1000000001
    if x <= median:
        heappush(lpq, -x)
        lsum += x
    else:
        heappush(rpq, x)
        rsum += x

    if len(rpq) + 1 < len(lpq):
        nxt = -heappop(lpq)
        heappush(rpq, nxt)
        lsum -= nxt
        rsum += nxt
    elif len(lpq) < len(rpq):
        nxt = heappop(rpq)
        heappush(lpq, -nxt)
        rsum -= nxt
        lsum += nxt

k, n = map(int, input().split())
same_side = 0
v = [(0, 0)]

for _ in range(n):
    a, x, b, y = input().split()
    x = int(x)
    y = int(y)
    if a == b:
        same_side += abs(x - y)
    else:
        v.append((x, y))

v.sort(key=cmp)
n = len(v) - 1
same_side += n

lsum = rsum = 0
pref = [0] * (n + 1)

for i in range(1, n + 1):
    insert(v[i][0])
    insert(v[i][1])
    pref[i] = rsum - lsum

ans = pref[n]

if k == 2:
    lpq.clear()
    rpq.clear()
    lsum = rsum = 0

    for i in range(n, 0, -1):
        insert(v[i][0])
        insert(v[i][1])
        ans = min(ans, rsum - lsum + pref[i - 1])

print(same_side + ans)

Compilation message (stdout)

Compiling 'bridge.py'...

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

=======

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37