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

#2514

[고등부] 2025 KOI 1차대회 대비 모의고사 (6주차)

교실 책상 배치 최적화
서브태스크
2초 512MB

문제

정올학교에는 총 m개의 교실이 있다.

각 교실에는 2n명의 학생이 있으며, 각각의 키가 주어진다.

모든 교실에는 교실마다 n개의 책상이 배치되는데 하나의 책상에는 두 명의 학생이 배정된다.

교실마다 다른 구성의 책상을 배치하는 것은 학생들이 싫어하므로
교실마다 같은 구성의 책상이 배치된다.

책상은 총 k종류가 있으며, 각 종류는 허용 가능한 키 범위를 정의한다.
책상 종류 i는 키가 L_i 이상 R_i 이하인 학생에게 적합하다.

이 범위를 벗어난 학생이 해당 책상에 앉으면 불편함을 느끼는데,
이때 불편함의 크기는 학생의 키와 범위 경계 중 가까운 값과의 차이의 절댓값으로 정의한다.

만약 학생의 키가 범위 안에 있다면, 불편함은 0이다.

예를 들어, 어떤 책상 종류의 범위가 L_i = 100, R_i = 120이라면,

  • 키가 80인 학생의 불편함은 20,

  • 키가 130인 학생의 불편함은 10,

  • 키가 105인 학생의 불편함은 0이다.


책상을 선택하고 학생들을 배치하는 방법을 최적화하여, 모든 그룹에 대해 학생들의 총 불편함 합계를 최소화해야 한다.

주어진 책상 종류와 각 교실의 학생 키 정보를 이용해,
최적의 책상 배치(배정)로 얻을 수 있는 최소 총 불편함을 계산하는 프로그램을 작성하라.


입력

첫 번째 줄에 세 개의 정수 m, n, k가 주어진다.
(1 \leq m, n \leq 200,000, 1 \leq m \times n \leq 200,000, 2 \leq k \leq 200,000)

  • m: 교실 수

  • n: 구입해야 할 책상 수

  • k: 구입 할 수 있는 책상 종류 수 (같은 종류 책상 여러 개 구매 가능)

이후 k줄에 걸쳐, 각 줄마다 두 개의 정수 L_i, R_i가 주어진다. (1 \leq L_i \leq R_i \leq 10^9)

  • 책상 종류 i가 적합한 학생 키 범위를 나타낸다.

이후 m줄에 걸쳐, 각 교실의 학생 키 정보가 주어진다.
각 줄마다 2n개의 정수 h_1, h_2, \ldots, h_{2n}이 주어지며, 이는 해당 교실의 각 학생 키를 나타낸다. (1 \leq h_i \leq 10^9)


출력

단 하나의 정수 P를 출력한다.

P는 책상을 최적으로 구매하고 학생들을 배치했을 때 얻을 수 있는 최소 총 불편함이다.


부분문제

번호 점수 조건
#110점

m \le 100, n = 1, k \le 50 

#210점

 m = 1, n \le 1000, k \le 50 

#310점

m \le 50, n \le 5, k \le 3 

#410점

m \le 100, n \le 1000, k =2 

#510점

m \le 100, n \le 1000, k \le 3 

#610점

m \le 100, n \le 1000, k \le 50 , L_i = R_i

#710점

m \le 100, n \le 1000, k \le 50 

#88점

L_i = R_i

#98점

m \le 100

#1010점

n \le 100

#114점

추가 제약 조건 없음


예제 #1

1 2 2
5 25
50 90
60 5 10 40
10

교실에 수업을 듣는 학생 그룹이 한 개뿐이다.
책상 종류별로 하나씩 구입하고, 다음과 같이 학생들을 배치할 수 있다:

  • 키 5와 10인 학생을 첫 번째 종류 책상에,

  • 키 40과 60인 학생을 두 번째 종류 책상에 배치.

이때, 키 40인 학생만 약간 불편하게 앉게 되며, 그의 불편함 값은 10이 된다.


예제 #2

2 3 3
100 600
200 400
300 500
30 40 300 300 330 440
150 250 300 350 450 550
130

예제 #3

1 3 4
10 100
200 200
10 100
300 1000
5 10 20 15 200 90
105
로그인해야 코드를 작성할 수 있어요.