IOI 2017- 전선 연결 > 문제은행 : 정보올림피아드&알고리즘




3630 : 전선 연결

제한시간
2000 ms   
메모리제한
256 MB   
해결횟수
2 회   
시도횟수
2 회   

문제

마얌은 전기 공학자 이다. 그녀는 통신 타워에서 전선 연결을 설계하고 있다. 

타워에는 서로 다른 높이들에 위치하는 연결점들이 존재한다. 

전선은 임의의 두 연결점을 연결하는데 사용될 수 있다. 

각 연결점은 임의개수의 전선들에 연결될 수 있다. 

두 가지 종류의 연결점들이 존재하는데 빨간점과 파란점이다. 

문제에서 타워는 직선으로, 연결점들은 직선 위 음이 아닌 정수 좌표에 놓인 빨간점과 파란점으로 생각한다. 

전선의 길이는 그것이 연결하는 두 연결점들 사이의 거리이다.

당신은 마얌이 다음을 만족하는 전선 연결 방식을 찾도록 도와야 한다:

 

1. 각 연결점은 자신과 다른 색깔의 연결점과 적어도 하나의 전선으로 연결되어야 한다.

2. 전선들의 총 길이가 최소화 되어야 한다.

 

빨간점과 파란점의 좌표가 주어지면 전선들의 총 길이의 최솟값을 구하는 프로그램을 작성하여라.

 


입력형식

첫 번째 줄에는 숫자, 알파벳으로 이루어진 길이 100 이하의 문자열이 주어진다. 해당 값은 의미없는 값이다.

두 번째 줄에는 N, M이 주어진다. (1 ≤ N, M ≤ 100,000)

세 번째 줄에는 빨간점의 좌표가 증가하는 순서대로 주어진다.

네 번째 줄에는 파란점의 좌표가 증가하는 순서대로 주어진다.

모든 점의 좌표는 0 이상 1,000,000,000 이하의 정수이며 서로 다르다.

 


출력형식

첫 번째 줄에 전선을 연결하는 최소 비용을 출력한다.

 


입력 예

JUNGOL
4 5
1 2 3 7
0 4 5 9 10

출력 예

10

출처

IOI 2017

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP