Submission #484232

#	Time	Username	Problem	Language	Result	Execution time	Memory
484232		beaconmc	Palembang Bridges (APIO15_bridge)	Pypy 3	22 / 100	535 ms	59400 KiB

bridge

import random
from statistics import *
from bisect import *
import math


sumz = 0
k,n = map(int, input().split())
bridges = []
cities = []
for i in range(n):
    a,b,c,d = input().split()
    b = int(b)
    d = int(d)
    if a!=c:
        bridges.append(b)
        bridges.append(d)
        cities.append([sorted([b, d]), abs(b-d)])
    else:
        sumz += abs(b-d)
    
if k==1:
    bridge = 0 if len(bridges)==0 else round(median(bridges))
else:
    sus = [round(i) for i in quantiles(bridges, n=4)]
    bridge = (sus[0], sus[2])


if k==1:
    for i in cities:
        if bridge<i[0][0]:
            sumz += (abs(i[0][0]-bridge))*2+1 + i[1]
        elif bridge>i[0][1]:
            sumz += (abs(i[0][1]-bridge))*2+1 + i[1]
        else:
            sumz += i[1]+1
else:
    for i in cities:
        if i[0][0]<bridge[0]<i[0][1] or i[0][0]<bridge[1]<i[0][1]:
            sumz += i[1]+1
        else:
            sumz += min((abs(i[0][0]-min(bridge)))*2+1 + i[1],(abs(i[0][1]-max(bridge)))*2+1 + i[1])
            
        
print(int(sumz))
    
        

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