원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
공장
원제: 공장
문제
어떤 공장이 일차 밤부터 일차 밤까지 가동될 예정이다. 공장의 근무는 매일 낮 시간대와 밤 시간대로 나누어 진행한다. 시간 순서대로 일차 밤, 일차 낮, 일차 밤, 일차 낮, 일차 밤, , 일차 낮, 일차 밤의 총 개의 시간대로 나뉘어 진행되며, 매 낮에는 주간 생산을, 매 밤에는 야간 경비를 진행한다.
공장 가동을 위해 명의 지원자 중에서 근무자를 골라 고용해야 한다. 번 지원자는 의 숙련도와 의 기여도를 가지고 있으며, 모든 지원자의 숙련도는 서로 다르다. 번 지원자를 고용하면 이 지원자는 일차 밤, 일차 낮, 일차 밤의 세 시간대에 근무하고, 그 대가로 의 기본 임금을 받는다. 즉, 고용된 근무자는 두 번의 야간 경비와 한 번의 주간 생산에 참여한다.
각 시간대의 업무는 그 시간대에 근무하는 모든 근무자를 숙련도가 작은 사람부터 큰 사람 순으로 한 줄로 세운 뒤, 줄의 앞에서부터 차례로 두 명씩 짝지어 진행한다. 즉, 근무자가 명이라면 정수 ()에 대해 줄의 번째 사람과 번째 사람이 짝이 된다.
모든 업무는 짝을 이뤄서만 진행할 수 있다. 따라서, 모든 시간대 각각에 대해 그 시간대에 근무하는 인원이 짝수 명이 되도록 근무자를 고용해야 한다. 근무하는 사람이 아무도 없는 시간대가 있어도 되며, 이 경우 그 시간대에는 아무 일도 일어나지 않는다.
진행하는 업무에 따라, 각 짝은 다음과 같은 결과를 만든다.
- 주간 생산: 낮에는 각 짝이 생산 라인을 가동해 제품을 만들며, 공장의 총 생산 이익을 변화시킨다. 구체적으로, 숙련도가 인 번과 번 지원자가 짝이 되면 총 생산 이익이 만큼 오른다. 이 값은 음수일 수도 있음에 유의하라.
- 야간 경비: 밤에는 각 짝이 조를 이뤄 공장 안팎을 순찰하며, 그 대가로 야간 수당을 지급받는다. 구체적으로, 숙련도가 인 번과 번 지원자가 짝이 되면 두 사람에게 합쳐서 의 야간 수당이 지급된다.
공장 가동 전 (일차 밤 이전), 공장의 총 생산 이익은 이다.
공장이 지급하는 총 임금은 고용한 근무자들의 기본 임금의 합과 모든 밤에 지급한 야간 수당의 합을 더한 값이다.
명의 지원자에 대한 정보가 주어질 때, 근무자를 적절히 고용하여 얻을 수 있는 "(총 생산 이익) (지급하는 총 임금)"의 최댓값과 그때 고용할 근무자의 목록을 구하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 정수 에 대하여
- 정수 에 대하여
- 정수 에 대하여
- 정수 에 대하여
- 의 값은 모두 서로 다르다.
부분문제
- (13점)
- (14점)
- (20점)
- (22점) 정수 ()에 대하여, 인 지원자의 수는 이하이다.
- (31점) 추가 제약 조건 없음.
입력 형식
첫 줄에 두 정수 과 가 공백으로 구분되어 차례대로 주어진다.
그다음 개의 줄에 걸쳐, 명의 지원자에 대한 정보가 주어진다. 이 중 번째 줄에는 번 지원자의 정보를 나타내는 네 정수 , , , 가 공백으로 구분되어 차례대로 주어진다.
출력 형식
첫 줄에 "(총 생산 이익) (지급하는 총 임금)"의 최댓값을 출력한다.
그다음 줄에 고용할 근무자의 수를 나타내는 정수 를 출력한다.
그다음 줄에 고용할 근무자 명의 번호를 공백으로 구분하여 임의의 순서로 출력한다. 인 경우, 빈 줄을 출력해도 되고, 이 줄을 출력하지 않아도 된다.
가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.
예제
예제 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
일차 낮에 근무하는 , 번 지원자와 일차 낮에 근무하는 , 번 지원자를 고용하는 것이 최적이다.
- 일차 낮에는 번과 번이 짝이 되어 총 생산 이익이 만큼 오른다.
- 일차 낮에는 번과 번이 짝이 되어 총 생산 이익이 만큼 오른다.
따라서 총 생산 이익은 이다.
- 일차 밤에는 번과 번이 짝이 되어 의 야간 수당이 지급된다.
- 일차 밤에는 네 명 모두가 근무하며, 숙련도 순서대로 번 (), 번 (), 번 (), 번 ()으로 줄을 세워, 번과 번, 번과 번이 각각 짝이 된다. 이 밤의 야간 수당은 이다.
- 일차 밤에는 번과 번이 짝이 되어 의 야간 수당이 지급된다.
따라서 야간 수당의 총합은 이다.
지급하는 총 임금은 기본 임금 에 야간 수당 을 더한 이고, 최종적으로 "(총 생산 이익) (지급하는 총 임금)"의 값은 이다.
위 예시에서, 일차 낮과 일차 밤의 짝이 서로 다르다는 점에 주목하라.
예제 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