2046번 - 이어달리기 다국어채점 준비 중
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 0 | 0 | 0 | 0.000% |
문제
이어달리기 경기가 서울에서 열린다. 경기 규칙은 다음과 같다.
- 각 팀은 정확히 N 명의 선수로 이루어진다.
- D 일 동안 가장 긴 거리를 달린 팀이 우승한다.
- 날마다 각 팀에서 한 명씩 달린다.
- 주자 교체는 하루가 시작될 때에만 가능하다.
- 각 팀에 소속된 선수는 최소 1일, 최대 3일을 달려야 한다.
- 한 번 교체된 선수는 다시 참가할 수 없다.
'칙칙폭폭' 팀이 이어달리기에 참가하기로 했다. '칙칙폭폭' 팀의 감독은 N 명의 선수가 D일 동안 경기에 나설 순서는 정했지만, 누가 정확히 며칠씩 달릴지는 아직 정하지 못했다. 감독은 각 선수의 기록을 보고서 누가 며칠씩 달릴지를 결정하고자 한다. 각 선수의 기록은 세 숫자로 이루어진다. i(i=1,2,3) 번째 숫자는 각 주자가 i 일 연속해서 달릴 때 갈 수 있는 거리를 나타낸다. (단위는 킬로미터.) 예를 들어 어느 선수의 기록이 (4,7,9)라면, 이 선수는 하루 달리면 4 킬로미터, 이틀 달리면 7 킬로미터, 사흘 달리면 9 킬로미터를 갈 수 있다. 모든 기록 (a,b,c)는 부등식 a ≤ b ≤ c을 만족한다.
감독은 '칙칙폭폭' 팀이 D일 동안 갈 수 있는 최장 거리를 알고 싶다. 예를 들어, N=3, D=4이고 세 선수의 기록이 (4,7,8), (2,4,6), (4,5,6)이라고 하자. 그렇다면 이 팀이 4일 동안 갈 수 있는 최장 거리는 13킬로미터이다. 첫 선수가 이틀 동안 (1,2 일차) 7 킬로미터, 둘째 선수가 하루 동안 (3 일차) 2 킬로미터, 셋째 선수가 하루동안 (4 일차) 4 킬로미터를 가면 된다.
'칙칙폭폭' 팀이 D 일 동안 갈 수 있는 최장거리를 알려주는 프로그램을 작성하라.
입력
입력은 T 개의 테스트 케이스로 구성된다. 입력 첫 줄에 테스트 케이스의 개수 T가 입력된다. 각 테스트 케이스는 N+2줄로 구성된다. 테스트 케이스의 첫 줄에는 '칙칙폭폭' 팀의 선수의 숫자를 나타내는 정수 N (1≤ N ≤ 50)이 주어진다. (단위는 명) 둘째 줄에는 이어달리기 대회가 진행되는 기간을 나타내는 정수 D (1≤ D ≤150)이 주어진다. (단위는 일) 이어서 N 줄 동안 각 선수의 기록이 주어진다. 선수의 기록이 주어지는 순서는 선수가 경기에 출전하는 순서이다.
출력
각 테스트 케이스마다 한 줄씩 출력한다. 각 줄에는 D 일 동안 달릴 수 있는 거리를 나타내는 정수 하나가 출력되어야 한다. 기록에 오류가 있거나, 대회 규칙에 따라 선수를 편성하는 것이 불가능 할 경우에는 -1을 출력한다.
예제 입력 1
2 3 4 4 7 8 2 4 6 4 5 6 2 7 2 3 5 3 6 8
예제 출력 1
13 -1
출처
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Seoul 2003 E번
- 문제를 번역한 사람: thebarbershop
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호