레이팅 미적용농부 존의 소 N마리(1 <= N <= 20)는 편의상 1...N으로 번호가 붙어 있으며, N개의 서로 다른 종목이 있는 10종 경기를 준비하고 있다.
소 i는 종목 j에 출전할 때 기량 수치 s_ij(1 <= s_ij <= 1000)를 가진다. 각 소는 정확히 하나의 종목에만 출전해야 하며, 각 종목에는 반드시 어떤 소가 출전해야 한다.
모든 소의 총점은 각 소가 출전한 종목에서의 기량 수치의 합이다. 그런데 심판들은 보너스 점수를 줄 수도 있다. 보너스는 B개(1 <= B <= 20) 있다. 보너스 i는 세 부분으로 이루어진다: 처음 K_i개의 종목에서 소들이 (그 종목들만 관련된 다른 보너스를 포함하여) 최소 P_i점(1 <= P_i <= 40,000)을 얻으면, 추가로 A_i점(1 <= A_i <= 1000)을 받는다.
총점을 최대화하려면 소들이 어떤 종목에 출전해야 하는지 결정하는 것을 도와라.
첫째 줄: 공백으로 구분된 두 정수 N, B
둘째 줄부터 B+1째 줄까지: i+1째 줄에는 보너스 i의 정보인 공백으로 구분된 세 정수 K_i, P_i, A_i가 주어진다.
B+2째 줄부터 B+N+1째 줄까지: B+1+j째 줄에는 소 j가 각 종목에서 내는 성적을 나타내는 N개의 공백으로 구분된 정수 s_j1...s_jN이 주어진다.
보너스를 포함하여 소들이 받을 수 있는 최대 점수를 출력한다.
dec.in · 출력을 쓸 파일 dec.out3 1
2 7 6
5 1 7
2 2 4
4 2 117Output details: Cow 1 does event 1, cow 3 does event 2, cow 2 does event 3, scoring 5+2+4 plus a 6-point bonus = 17.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > February > Gold