레이팅 미적용August 8 – 15, Plovdiv, Bulgaria
Contest Day 2 - Salesman
English 1.2
외판원 (SALESMAN)
외판원은 육지에서의 여행 일정을 최적으로 짜는 것이 다루기 힘든 계산 문제라고 판단하여, 사업을 도나우강이라는 선형 세계로 옮기기로 했다. 그에게는 강을 따라 어디서든 어디로든 순식간에 데려다줄 수 있는 매우 빠른 배가 있지만, 안타깝게도 연비가 끔찍하다. 상류(강의 발원지 방향)로 1미터 이동할 때마다 U 달러, 하류(발원지에서 멀어지는 방향)로 1미터 이동할 때마다 D 달러가 든다.
외판원이 방문하고 싶은 무역 박람회가 강을 따라 N개 있다. 각 박람회는 하루만 열린다. 각 박람회 X에 대해, 외판원은 배를 산 날로부터 며칠째인지로 측정한 날짜 TX를 안다. 또한 강의 발원지에서 하류로 몇 미터 떨어져 있는지로 측정한 박람회의 위치 LX와, 이 박람회에 참가하면 벌게 될 달러 액수 MX도 안다. 그는 강가에 있는 자신의 집에서 여행을 시작하고 끝내야 하며, 집의 위치는 발원지에서 하류로 S 미터 지점이다.
외판원이 여행이 끝났을 때의 이익을 최대화할 수 있도록, 어느 박람회에 (참가한다면) 어떤 순서로 참가할지 선택하는 것을 도와주시오. 외판원의 총이익은 참가한 박람회들에서 번 달러의 합에서, 강을 오르내리며 쓴 달러의 총합을 뺀 값으로 정의된다.
박람회 A가 박람회 B보다 먼저 열리면 외판원은 이 순서로만 방문할 수 있음에 유의하라(즉, B를 방문한 뒤 A를 방문할 수 없다). 하지만 두 박람회가 같은 날에 열리면 어느 순서로든 둘 다 방문할 수 있다. 하루에 방문할 수 있는 박람회 수에는 제한이 없지만, 당연히 같은 박람회를 두 번 방문해서 이익을 두 번 얻을 수는 없다. 이미 방문한 박람회는 아무것도 얻지 못한 채 지나갈 수 있다.
TASK
모든 박람회의 날짜, 위치, 수익성, 그리고 외판원의 집 위치와 이동 비용이 주어졌을 때, 여행이 끝났을 때 그가 낼 수 있는 최대 이익을 구하는 프로그램을 작성하시오.
EXAMPLE
Sample Input
Sample Output
4 5 3 100
2 80 100
20 125 130
10 75 150
5 120 110
50
최적의 일정은 박람회 1과 3(위치 80과 75에 있는 것들)을 방문하는 것이다. 사건들의 순서와 그에 따른 이익과 비용은 다음과 같다:
외판원은 상류로 20미터 이동하며 100달러를 쓴다. 지금까지의 이익: -100
박람회 1에 참가하여 100을 번다. 지금까지의 이익: 0
상류로 5미터 이동하며 25를 쓴다. 지금까지의 이익: -25
박람회 3에 참가하여 150을 번다. 지금까지의 이익: 125
집으로 돌아가기 위해 하류로 25미터 이동하며 75를 쓴다. 최종 이익: 50
\(1 \le N \le 500,000\)
박람회의 수
\(1 \le D \le U \le 10\)
상류(U) 또는 하류(D)로 1미터 이동하는 비용
\(1 \le S \le 500,001\)
외판원의 집 위치
\(1 \le Tk \le 500,000\)
박람회 k가 열리는 날
\(1 \le Lk \le 500,001\)
박람회 k의 위치
\(1 \le Mk \le 4,000\)
박람회 k에 참가하면 외판원이 벌게 될 달러 액수
August 8 – 15, Plovdiv, Bulgaria
Contest Day 2 - Salesman
English 1.2
프로그램은 표준 입력에서 다음 데이터를 읽어야 한다:
• 첫 줄에는 정수 N, U, D, S가 이 순서로 공백 하나씩으로 구분되어 주어진다.
• 다음 N개의 줄에는 N개의 박람회가 특별한 순서 없이 주어진다. 이 N개의 줄 중 k번째 줄은 k번째 박람회를 나타내며, 공백 하나씩으로 구분된 세 정수가 있다: 박람회의 날짜 Tk, 위치 Lk, 그리고 외판원에게 주는 수익 Mk.
NOTE: 입력으로 주어지는 모든 위치는 서로 다르다. 즉, 같은 위치에서 열리는 두 박람회는 없으며, 외판원의 집에서 열리는 박람회도 없다.
프로그램은 표준 출력에 정수 하나가 있는 한 줄을 출력해야 한다: 여행이 끝났을 때 외판원이 낼 수 있는 최대 이익.
GRADING
총 60점에 해당하는 여러 테스트에서는 같은 날에 열리는 두 박람회가 없다.
총 40점에 해당하는 여러 테스트에서는 입력의 어떤 수도 5,000을 넘지 않는다.
위 두 조건이 모두 성립하는 테스트는 15점에 해당한다.
두 조건 중 적어도 하나가 성립하는 테스트는 85점에 해당한다.