頁面無法載入？點擊這裡可能會修復。
Placeholder

#8458
子任務

교실 책상 배치 최적화 2s 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


來源

Russian Olympiad in Informatics 2019 Классные парты

需要登入才能撰寫程式碼。