루미 알고리즘

#1141다이아공장공장

KOI 2026 2차코딩고등부 4번출제 송준혁이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

공장

원제: 공장

문제

어떤 공장이 00일차 밤부터 TT일차 밤까지 가동될 예정이다. 공장의 근무는 매일 낮 시간대와 밤 시간대로 나누어 진행한다. 시간 순서대로 00일차 밤, 11일차 낮, 11일차 밤, 22일차 낮, 22일차 밤, ⋯\cdots, TT일차 낮, TT일차 밤의 총 2T+12T + 1개의 시간대로 나뉘어 진행되며, 매 낮에는 주간 생산을, 매 밤에는 야간 경비를 진행한다.

공장 가동을 위해 NN명의 지원자 중에서 근무자를 골라 고용해야 한다. ii (1≤i≤N)(1 \le i \le N)번 지원자는 AiA_i의 숙련도와 BiB_i의 기여도를 가지고 있으며, 모든 지원자의 숙련도는 서로 다르다. ii번 지원자를 고용하면 이 지원자는 Di−1D_i - 1일차 밤, DiD_i일차 낮, DiD_i일차 밤의 세 시간대에 근무하고, 그 대가로 CiC_i의 기본 임금을 받는다. 즉, 고용된 근무자는 두 번의 야간 경비와 한 번의 주간 생산에 참여한다.

각 시간대의 업무는 그 시간대에 근무하는 모든 근무자를 숙련도가 작은 사람부터 큰 사람 순으로 한 줄로 세운 뒤, 줄의 앞에서부터 차례로 두 명씩 짝지어 진행한다. 즉, 근무자가 2k2k명이라면 정수 jj (1≤j≤k1 \le j \le k)에 대해 줄의 2j−12j - 1번째 사람과 2j2j번째 사람이 짝이 된다.

모든 업무는 짝을 이뤄서만 진행할 수 있다. 따라서, 모든 시간대 각각에 대해 그 시간대에 근무하는 인원이 짝수 명이 되도록 근무자를 고용해야 한다. 근무하는 사람이 아무도 없는 시간대가 있어도 되며, 이 경우 그 시간대에는 아무 일도 일어나지 않는다.

진행하는 업무에 따라, 각 짝은 다음과 같은 결과를 만든다.

  • 주간 생산: 낮에는 각 짝이 생산 라인을 가동해 제품을 만들며, 공장의 총 생산 이익을 변화시킨다. 구체적으로, 숙련도가 Ax>AyA_x > A_y인 xx번과 yy번 지원자가 짝이 되면 총 생산 이익이 Bx−ByB_x - B_y만큼 오른다. 이 값은 음수일 수도 있음에 유의하라.
  • 야간 경비: 밤에는 각 짝이 조를 이뤄 공장 안팎을 순찰하며, 그 대가로 야간 수당을 지급받는다. 구체적으로, 숙련도가 Ax>AyA_x > A_y인 xx번과 yy번 지원자가 짝이 되면 두 사람에게 합쳐서 Ax−AyA_x - A_y의 야간 수당이 지급된다.

공장 가동 전 (00일차 밤 이전), 공장의 총 생산 이익은 00이다.

공장이 지급하는 총 임금은 고용한 근무자들의 기본 임금의 합과 모든 밤에 지급한 야간 수당의 합을 더한 값이다.

NN명의 지원자에 대한 정보가 주어질 때, 근무자를 적절히 고용하여 얻을 수 있는 "(총 생산 이익) −- (지급하는 총 임금)"의 최댓값과 그때 고용할 근무자의 목록을 구하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤T≤N≤5001 \le T \le N \le 500
  • 정수 ii (1≤i≤N)(1 \le i \le N)에 대하여 0≤Ai≤1 0000 \le A_i \le 1\,000
  • 정수 ii (1≤i≤N)(1 \le i \le N)에 대하여 0≤Bi≤1 0000 \le B_i \le 1\,000
  • 정수 ii (1≤i≤N)(1 \le i \le N)에 대하여 0≤Ci≤1 0000 \le C_i \le 1\,000
  • 정수 ii (1≤i≤N)(1 \le i \le N)에 대하여 1≤Di≤T1 \le D_i \le T
  • A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N의 값은 모두 서로 다르다.

부분문제

  1. (13점) N≤20N \le 20
  2. (14점) T=1T = 1
  3. (20점) T≤10T \le 10
  4. (22점) 정수 dd (1≤d≤T1 \le d \le T)에 대하여, Di=dD_i = d인 지원자의 수는 88 이하이다.
  5. (31점) 추가 제약 조건 없음.

입력 형식

첫 줄에 두 정수 NN과 TT가 공백으로 구분되어 차례대로 주어진다.

그다음 NN개의 줄에 걸쳐, NN명의 지원자에 대한 정보가 주어진다. 이 중 ii (1≤i≤N)(1 \le i \le N)번째 줄에는 ii번 지원자의 정보를 나타내는 네 정수 AiA_i, BiB_i, CiC_i, DiD_i가 공백으로 구분되어 차례대로 주어진다.

출력 형식

첫 줄에 "(총 생산 이익) −- (지급하는 총 임금)"의 최댓값을 출력한다.

그다음 줄에 고용할 근무자의 수를 나타내는 정수 KK를 출력한다.

그다음 줄에 고용할 근무자 KK명의 번호를 공백으로 구분하여 임의의 순서로 출력한다. K=0K = 0인 경우, 빈 줄을 출력해도 되고, 이 줄을 출력하지 않아도 된다.

가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.

예제

예제 1

입력
6 2
21 0 1 1
13 25 0 2
22 20 3 2
20 5 2 2
4 23 0 2
25 16 8 1
출력
7
4
1 3 4 6

11일차 낮에 근무하는 11, 66번 지원자와 22일차 낮에 근무하는 33, 44번 지원자를 고용하는 것이 최적이다.

  • 11일차 낮에는 11번과 66번이 짝이 되어 총 생산 이익이 B6−B1=16B_6 - B_1 = 16만큼 오른다.
  • 22일차 낮에는 44번과 33번이 짝이 되어 총 생산 이익이 B3−B4=15B_3 - B_4 = 15만큼 오른다.

따라서 총 생산 이익은 16+15=3116 + 15 = 31이다.

  • 00일차 밤에는 11번과 66번이 짝이 되어 A6−A1=4A_6 - A_1 = 4의 야간 수당이 지급된다.
  • 11일차 밤에는 네 명 모두가 근무하며, 숙련도 순서대로 44번 (A4=20A_4 = 20), 11번 (A1=21A_1 = 21), 33번 (A3=22A_3 = 22), 66번 (A6=25A_6 = 25)으로 줄을 세워, 44번과 11번, 33번과 66번이 각각 짝이 된다. 이 밤의 야간 수당은 (A1−A4)+(A6−A3)=1+3=4(A_1 - A_4) + (A_6 - A_3) = 1 + 3 = 4이다.
  • 22일차 밤에는 33번과 44번이 짝이 되어 A3−A4=2A_3 - A_4 = 2의 야간 수당이 지급된다.

따라서 야간 수당의 총합은 4+4+2=104 + 4 + 2 = 10이다.

지급하는 총 임금은 기본 임금 1+3+2+8=141 + 3 + 2 + 8 = 14에 야간 수당 1010을 더한 2424이고, 최종적으로 "(총 생산 이익) −- (지급하는 총 임금)"의 값은 31−24=731 - 24 = 7이다.

위 예시에서, 11일차 낮과 11일차 밤의 짝이 서로 다르다는 점에 주목하라.

예제 2

입력
5 2
40 23 10 1
59 22 2 2
32 7 10 2
52 30 0 1
38 10 3 1
출력
0
0

아무도 고용하지 않는 것이 최적이다.

예제 3

입력
12 3
6 19 4 2
32 0 1 3
12 0 4 3
25 7 0 2
35 15 5 1
28 25 5 2
19 27 3 3
30 13 3 2
1 24 5 3
20 11 0 2
2 1 5 2
24 28 3 2
출력
20
8
1 3 4 6 7 10 11 12

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.