레이팅 미적용베시는 Bovine Genomics: The Documentary를 보고 싶지만, 혼자 가고 싶지는 않다. 안타깝게도 친구들은 베시와 함께 갈 만큼 열의가 없다! 그래서 베시는 친구들을 매수해서 영화관에 같이 가야 한다. 베시의 매수 수단은 두 가지, 무니(mooney)와 아이스크림 콘이다.
베시에게는 \(N\)명(\(1 \le N \le 2000\))의 친구가 있다. 하지만 모든 친구가 똑같지는 않다! 친구 \(i\)는 인기 점수 \(P_i\) (\(1 \le P_i \le 2000\))를 가지며, 베시는 동행하는 친구들의 인기 점수의 합을 최대화하고 싶다. 친구 \(i\)는 베시가 무니 \(C_i\)개(\(1 \le C_i \le 2000\))를 주어야만 동행할 의향이 있다. 또한 베시가 아이스크림 콘 \(X_i\)개(\(1 \le X_i \le 2000\))를 주면 무니 \(1\)개를 할인해 준다. 베시는 할인 때문에 친구가 오히려 베시에게 무니를 주게 되지 않는 한, 한 친구에게서 정수 단위의 할인을 원하는 만큼 받을 수 있다.
베시가 쓸 수 있는 무니는 \(A\)개, 아이스크림 콘은 \(B\)개이다(\(0 \le A, B \le 2000\)). 베시가 무니와 아이스크림 콘을 최적으로 쓸 때 얻을 수 있는 인기 점수 합의 최댓값을 구하시오!
출제: Timothy Feng, Nathan Wang, and Sam Zhang
배점
- 테스트 케이스 2-4는 \(N \leq 5\)와 \(C_i = 1\)을 만족한다.
- 테스트 케이스 5-7은 \(B = 0\)을 만족한다.
- 테스트 케이스 8-10은 \(N, A, B, P_i, C_i, X_i \leq 50\)을 만족한다.
- 테스트 케이스 11-15는 \(N, A, B, P_i, C_i, X_i \leq 200\)을 만족한다.
- 테스트 케이스 16-20은 추가 제약이 없다.
출제: Timothy Feng, Nathan Wang, and Sam Zhang
첫째 줄에 세 수 \(N\), \(A\), \(B\)가 주어지며, 각각 친구의 수, 베시가 가진 무니의 개수, 아이스크림 콘의 개수를 나타낸다.
다음 \(N\)개의 줄에는 각각 세 수 \(P_i\), \(C_i\), \(X_i\)가 주어지며, 각각 인기 점수(\(P_i\)), 친구 \(i\)를 매수하여 동행시키는 데 필요한 무니(\(C_i\)), 친구 \(i\)에게서 무니 \(1\)개를 할인받는 데 필요한 아이스크림 콘의 개수(\(X_i\))를 나타낸다.
베시가 무니와 아이스크림 콘을 최적으로 쓴다고 할 때, 동행하는 친구들의 인기 점수 합의 최댓값을 출력한다.
3 10 8
5 5 4
6 7 3
10 6 315Bessie can give \(4\) moonies and \(4\) ice cream cones to cow \(1\), and \(6\) moonies
and \(3\) ice cream cones to cow \(3\), in order to get cows \(1\) and \(3\) to
accompany her for a total popularity of \(5 + 10 = 15\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > December > Gold