시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 222 | 89 | 71 | 36.598% |
홍익대학교 서울 캠퍼스의 건물들은 정문부터 후문까지 연결되어 있지만 건물마다 연결되어 있는 층이 제각각이다. 예를 들어 정문인 R동의 3층으로 나오면 K동의 1층이 있고, L동의 8층으로 나오면 I동의 1층이 있기도 하다. 이렇듯 캠퍼스가 작지만 복잡하게 연결되어 있어 학생들 사이에선 '홍그와트'라는 별명으로 불리고 있다.
건축공학과 학생인 기열이는 이러한 특징이 잘 드러나도록 정문부터 후문까지 연결된 홍익대학교의 지하 캠퍼스를 설계하여 과제로 제출해야 한다. 하지만 기열이는 자기 손으로 과제를 끝내기에 턱없이 시간이 모자란다고 생각하고 포기하기 직전에 놓여있다. 절망에 빠진 기열이를 위해 희망을 주도록 하자.
기열이를 위해 유명한 건물 모델 사이트에서 M개의 모델을 가져왔다. 해당 모델들은 바로 3D프린터로 출력할 수 있으며, 이 모델들을 이어 붙이기만 하면 과제를 완성할 수 있도록 되어있다. 또한 모든 모델은 좌우로 뒤집어 사용할 수 있도록 만들어졌다. (단 위아래가 바뀌도록 뒤집을 수는 없다.)
샘플의 높이를 맘대로 바꿀 수는 없지만 너비를 바꾸는 것은 매우 쉬운 일이기 때문에 건물을 몇 개나 사용하는지는 중요하지 않다고 할 때, 캠퍼스를 설계할 때 드는 최소 시간을 구해서 기열이에게 알려주자.
위와 같이 3개의 모델이 주어진다고 했을 때, 각각 H, T, E1, E2값은 각각 모델 아래 박스 안의 값과 같다.
N=9, R=3, D=2 라고 할 때, 위 세 모델로 캠퍼스를 설계한다면 시간을 최소로 하는 설계 방법은 아래 그림과 같다.
이 때 걸리는 시간은 38이다.
첫 째 줄에는 건물을 배치할 수 있는 지하 층 수에 해당하는 자연수 N이 주어진다. ( N은 2 ≤ N ≤ 2,000 이다. )
둘 째 줄에는 각각 정문과 후문에 출입구가 위치한 층 R과 D가 공백을 사이에 두고 주어진다. ( R과 D는 각각 1 ≤ R ≤ N, 1 ≤ D ≤ N 인 자연수다. )
셋 째 줄에는 샘플의 개수 M이 주어진다. ( M은 1 ≤ M ≤ 2,000 인 자연수다. )
넷 째 줄부터 M+3번째 줄까지 각 줄에는 샘플의 꼭대기 층 Hi, 수정하는데 걸리는 시간 Ti, 출입구가 있는 층 Ei1, Ei2가 각각 공백을 사이에 두고 주어진다.
( 이 때 위의 입력은 각각 2 ≤ Hi ≤ N, 1 ≤Ti ≤ 1,000,000, 1 ≤ Ei1 ≤ Hi , 1 ≤ Ei2 ≤ Hi 를 만족하는 자연수이다. 단, Ei1 ≠ Ei2 이다. )
첫 째 줄에 과제를 끝마치기 위해 필요한 최소 시간을 출력하라.
단, 주어진 모델로 캠퍼스를 설계할 수 없다면 첫 째 줄에 -1을 출력하라.
9 3 2 3 8 10 7 2 8 20 4 3 5 14 1 3
34
University > 홍익대학교 > 2019 홍익대학교 프로그래밍 경진대회 K번