페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5837
서브태스크

조이 4인조 (JOI04) 2s 1024MB

문제

JOI 중학교에는 4N 명의 1학년이 재적하고 있어 4개의 반으로 나누어져 있다. 각 반의 정보는 다음과 같다.

  • 1학년 A반: N명의 학생이 있다. 각 학생의 키는 A_ 1 , A _2 , ..., A _N 다.

  • 1학년 B반: N명의 학생이 있다. 각 학생의 키는 B _1 , B _2 , ..., B _N 다.

  • 1학년 C반: N명의 학생이 있다. 각 학생의 키는 C _1 , C _2 , ..., C _N 다.

  • 1학년 D반: N명의 학생이 있다. 각 학생의 키는 D _1 , D _2 , ..., D _N 다.

다음 달 JOI 중학교에서는 체육대회가 개최된다. 그 중 각 학년이 춤추는 댄스는 체육대회의 꽃이라고 불리는 종목이다.

여기서 1학년은, 각 반들로부터 대표를 한 명씩 선택해, 4명이서 댄스를 하게 되었다. 댄스팀의 비주얼을 가능한 한 좋게 하기 위해 키의 차이가 가능한 한 작아지도록 4명을 선택하기로 했다.

1학년의 신장이 주어질 때, 네 명의 키의 최대치와 네 명의 키의 최소치의 차이의 최소를 구하는 프로그램을 작성하라.


입력

입력은 다음 형식으로 제공된다.

N

A_ 1 , A _2 , ..., A _N

B _1 , B _2 , ..., B _N
C _1 , C _2 , ..., C _N
D _1 , D _2 , ..., D _N

[제한]

1 ≦ N ≦ 75,000．

1 ≦ A i ≦ 10 ^9 ( 1 ≦ i ≦ N )．

1 ≦ B j ≦ 10 ^9 ( 1 ≦ j ≦ N )．

1 ≦ C k ≦ 10 ^9 ( 1 ≦ k ≦ N )．

1 ≦ D l ≦ 10 ^9 ( 1 ≦ l ≦ N )．

입력 된 모든 값은 정수입니다.


출력

「4 명의 신장의 최대치」와 「4 명의 신장의 최소치」의 차로서 생각할 수 있는 최소의 값을 1 행으로 출력하라.


부분문제

번호 점수 조건
#17점

N = 1

#223점

N ≦ 30

#314점

N≤2\,000, A_i≤10 , B_j≤10, C_k≤10, D_l≤10 (1≤i,j,k,l≤N)

#420점

N≤2\,000, A_i≤2\,000 , B_j≤2\,000, C_k≤2\,000, D_l≤2\,000 (1≤i,j,k,l≤N)

#513점

N≤2\,000

#623점

추가 제한 없음


예제 #1

1
169
173
152
200
48

N = 1 이므로 모든 학생을 선택하여 4 인조를 만들어야 한다. 이 때 4 명의 신장의 최대 값은 200 , 최소값은 152 이며, 그 차이는 200 - 152 = 48 이다. 따라서 48 을 출력한다.

이 입력 예제는 서브태스크 1, 2, 4, 5, 6 의 제약 조건을 충족한다.


예제 #2

7
7 9 9 4 6 3 5
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
2

이 입력 예제는 서브태스크 2, 3, 4, 5, 6 의 제약 조건을 충족한다.


예제 #3

7
1 1 1 1 2 1 1
1 2 1 1 1 1 1
1 1 1 1 2 1 1
1 1 1 1 1 1 2
0

이 입력 예제는 서브태스크 2, 3, 4, 5, 6 의 제약 조건을 충족한다.


예제 #4

5
287 690 413 420 138
813 873 223 415 907
261 330 361 747 787
958 672 544 126 345
70

이 입력 예제는 서브태스크 2, 4, 5, 6 의 제약 조건을 충족한다.


예제 #5

10
1682 2008 1135 1576 2450 1362 1518 1925 2212 1275
1993 1945 1312 1401 2027 1705 1086 2333 1787 1654
2257 1548 1219 1031 2613 2171 1866 1532 2800 1497
1062 1175 1984 1870 2059 1639 2107 1335 1289 2494
79

이 입력 예는 서브태스크 2, 5, 6 의 제약 조건을 충족한다.



출처

JOI 2023 예선2
로그인해야 코드를 작성할 수 있어요.