키위 주스 > 문제은행

본문 바로가기


알고리즘 다이나믹2

2356 : 키위 주스

제한시간: 2000 ms    메모리제한: 128 MB
해결횟수: 107 회    시도횟수: 273 회   



0부터 N - 1까지 번호가 차례로 매겨진 눈금 없는 병이 있다. 각 병의 용량은 C 리터로 모두 같다.

 

이 병들에 각각 병에 Bi 리터씩의 키위 주스를 담았다. 이 키위 주스들을 판매하려고 하는데, 그 전에 주스들을 서로 옮겨 담을 수 있다. 즉, 서로 다른 두 병 A와 B를 골라 A 병에서 B 병으로 주스를 옮겨 담아 A가 비거나 B가 가득찰 때까지 옮기는 것이다. 이렇게 옮겨 담은 병의 가치는 x리터가 담긴 병에 대해 Px 달러이다. 모든 병의 가치의 총 합을 최대화하라.


입력은 세 줄로 구성된다. 첫 줄에는 C와 N이 공백으로 구분되어 주어진다. 다음 줄에는 각 병에 담긴 주스의 양인 Bi가 공백으로 구분되어 주어진다. 마지막 줄에는 병에 담긴 용량에 따른 가치인 Pi 가 공백으로 구분되어 주어진다. 입력 예를 참고하라.

제약 조건 - C 는 1 이상 49 이하의 정수이다. - N 은 1 이상 15 이하의 정수이다. - Bi 는 0 이상 C 이하의 정수이다. - Pi 는 0 이상 106 이하의 정수이다.



입력에 대한 최대 가치를 구하여 하나의 행에 출력한다.


[Copy]
10 2
5 8
0 0 0 0 0 0 0 0 0 0 10
[Copy]
10


[Copy]
10 2
5 8
0 0 0 0 0 10 10 10 10 10 10
[Copy]
20


[Copy]
10 4
4 5 3 7
14 76 12 35 6 94 26 3 93 90 420
[Copy]
625


[Copy]
1 1
0
1000000 1000000
[Copy]
1000000


출처 : PR



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.