18768번 - 팀 배정 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.7 초 | 256 MB | 200 | 82 | 56 | 35.669% |
문제
사내 해커톤 대회에서 팀 배틀 보안 해커톤을 하기로 했다.
대회는 주어진 보안 서버를 공격(해킹)하는 역할의 팀 A와 방어(보안)하는 역할의 팀 B로 나누어서 진행한다. 참가자는 총 n명이고, 각 참가자의 공격 능력과 방어 능력은 검증된 사내 테스트를 통해 수치화 되어있다.
참가자는 1부터 n까지 번호가 매겨져 있고, Ai, Bi는 양의 정수로 참가자 i의 공격 능력과 방어 능력을 의미한다.
n명의 참가자를 팀 A와 팀 B로 아래 조건을 지키면서 나누어야 한다.
- 두 팀에 배정된 참가자 수의 차이는 k 이하가 되어야 한다.
- 각 참가자는 두 팀 중 하나에 반드시 속해야한다.
- 위의 두 조건을 만족하는 모든 팀 배정 방법 중, 팀 A에 배정된 참가자들의 공격 능력 총 합과 팀 B에 배정된 참가자들의 방어 능력치 총 합이 최대가 되어야 한다.
예를 들어, n = 3, k = 1이고, 세 참가자의 공격 능력과 방어 능력이 아래와 같은 경우를 살펴보자.
- A1 = 1, B1 = 100
- A2 = 100, B2 = 99
- A3 = 80, B3 = 95
k = 1이기 때문에, 팀 A와 팀 B에는 각각 1명과 2명이 배정되어야 한다.
총 여섯 가지 방법이 가능하며 팀 구성과 능력치의 합은 아래와 같다.
- 팀 A: [1], 팀 B: [2, 3], 능력치의 합 = A1 + B2 + B3 = 195
- 팀 A: [2], 팀 B: [1, 3], 능력치의 합 = A2 + B1 + B3 = 295
- 팀 A: [3], 팀 B: [1, 2], 능력치의 합 = A3 + B1 + B2 = 279
- 팀 A: [2, 3], 팀 B: [1], 능력치의 합 = A2 + A3 + B1 = 280
- 팀 A: [1, 3], 팀 B: [2], 능력치의 합 = A1 + A3 + B2 = 180
- 팀 A: [1, 2], 팀 B: [3], 능력치의 합 = A1 + A2 + B3 = 196
두 번째 방법이 가장 높은 능력치 합을 가진다.
n, k, 그리고 각 참가자의 공격과 방어 능력치가 주어졌을 때, 가능한 모든 팀 배정 방식 중에서 능력치 합의 최댓값을 구해보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫째 줄에는 n과 k가 공백으로 구분되어 주어진다. 둘째 줄에는 참가자의 공격 능력을 나타내는 A1, A2, ..., An이 주어지고, 셋째 줄에는 방어 능력을 나타내는 B1, B2, ..., Bn이 주어진다.
출력
각 테스트 케이스 마다 능력치 합의 최댓값을 한 줄에 하나씩 출력한다.
제한
- 1 ≤ T ≤ 10
- 3 ≤ n ≤ 100,000
- 1 ≤ k ≤ n-2
- 1 ≤ Ai, Bi ≤ 1,000,000
예제 입력 1
4 5 2 1 2 3 4 5 2 3 4 5 6 5 3 1 2 3 4 5 5 4 3 2 1 5 2 1 3 5 7 9 1 2 3 4 5 3 1 1 100 80 100 99 95
예제 출력 1
18 21 24 295
- 테스트 케이스 1: A1 + A2 + B3 + B4 + B5 = 18
- 테스트 케이스 2: B1 + B2 + A3 + A4 + A5 = 21
- 테스트 케이스 3: B1 + B2 + A3 + A4 + A5 = 24
- 테스트 케이스 4: 문제에서 다룬 예시
힌트
능력치 총 합이 231-1 보다 클 수 있다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호