이번 문제는 그리디 알고리즘을 활용하여 해결하였다. 우선 학교를 기준으로 왼쪽과 오른쪽에 위치한 아파트를 서로 다른 최소힙에 넣어 관리하였다. 이는 학교로부터의 거리가 먼 순서대로 추출하기 위함이기 때문에 오른쪽에 위치한 아파트들의 위치정보는 음수로 넣어 최대힙으로 이용하였다.

이제 최소힙을 각각 추출하며 현재 위치의 인원들을 버스에 모두 태울 수 있을 때 버스의 인원을 증가시키고, 학교로 돌아가는 길에 다른 인원을 더 태울 수 있기 때문에 이번 이동에서의 최대 거리를 dist로 저장한다. 그리고 이번이 마지막 위치일 수 있으므로 그럴 경우 현재의 위치를 2배한 값을 결과값에 더하도록 하였다. 인원을 모두 태울 수 없다면 최소힙에 현재 위치와 남은 인원을 튜플로 묶어 다시 넣어주고, 만약 dist가 0일 경우 현재 위치와 학교 사이의 거리를 2배하여 결과 변수에 더한다. 그렇지 않다면 dist를 2배한 값을 결과 변수에 더하였다.

이와 같은 방법으로 left, right에 대하여 반복하여 결과를 구하였다.

Code

import heapq
n, k, s = map(int, input().split())
apt = [list(map(int, input().split())) for _ in range(n)]
answer = 0
left, right = [], []
for i in range(n):
    if apt[i][0] <= s:
        heapq.heappush(left, (apt[i][0], apt[i][1]))
    else:
        heapq.heappush(right, (-apt[i][0], apt[i][1]))
bus = 0
dist = 0
while left:
    l, p = heapq.heappop(left)
    if (k-bus) >= p:
        bus += p
        dist = max(dist, s-l)
        if not left:
            answer += dist*2
    else:
        heapq.heappush(left, (l, p-(k-bus)))
        if dist == 0:
            answer += (s-l)*2
        else:
            answer += dist*2
            dist = 0
        bus = 0
bus = 0
dist = 0
while right:
    l, p = heapq.heappop(right)
    l = -l
    if (k-bus) >= p:
        bus += p
        dist = max(dist, l-s)
        if not right:
            answer += dist*2
    else:
        heapq.heappush(right, (-l, p-(k-bus)))
        if dist == 0:
            answer += (l-s)*2
        else:
            answer += dist*2
            dist = 0
        bus = 0
print(answer)