약 > 문제은행



문제은행

3389 : 약

제한시간: 2000 ms    메모리제한: 512 MB
해결횟수: 2 회    시도횟수: 37 회   



 

수빈이에게도 어김없이 과제폭탄이 떨어졌다! 

연속된 밤샘으로 몸이 녹초가 된 수빈이는 바람도 쐴 겸 동네 놀이터로 갔다. 

놀랍게도 놀이터에 N개의 약이 떨어져 있었다. 

수빈이는 이 약을 먹으면 바닥난 에너지를 채울 수 있다는 생각에 떨어진 약 하나를 주워서 입에 털어 넣었다. 

조금이 정신이 나아지나 싶더니.......

 

수빈이는 약의 효과로 이리저리 움직이며 춤을 추기 시작했다. 

그는 자기 몸을 가누지 못한 채 그저 자신이 움직이는 방향(왼쪽 혹은 오른쪽)만 조절할 수 있었다. 

수빈이가 약발이 지속되는 동안 약이 있는 장소를 지나면 수빈이 자신도 모르게 그 약을 먹게 되어 새롭게 약의 효과가 지속된다. 

한 번 먹은 약은 사라지므로 한 약을 여러 번 먹을 수 없으며 약을 이미 먹었던 지역은 별 문제 없이 지나갈 수 있다.

 

수빈이는 약발이 끊기지 않은 채 N개의 약을 연달아 먹어버리고 말았다! 

수빈이가 약이 깨고 놀이터 어딘가에서 제정신을 차렸을 때, 

그는 자신도 모르는 사이에 놀이터의 관중들 앞에서 인싸댄스를 발휘했다는 생각에 충격을 먹었다. 

그러나 그것도 잠시, 수빈이는 ‘댄스는 나의 숙명’이라는 책임감을 떠안고 충격이 가라앉았다. 

그러나 진짜 문제는 약에 다른 부작용이 있다면 수빈이의 건강에 큰 악영향을 끼친다는 것이다.

 

수빈이가 이 약에 대하여 찾아본 결과, 왼쪽에서 i번째 약을 정확히 Ci번째에 먹는다면 Di만큼 데미지를 입는다는 사실을 파악했다. 

이를 통해 수빈이는 자신이 입은 데미지의 총합이 얼마나 큰지 계산해보려고 한다. 

건강을 걱정하는 수빈이를 위해 i번째 약을 가장 먼저 먹었을 때 최대 얼마의 데미지를 입는지 구하는 프로그램을 작성하여라.

 




첫 번째 줄에는 약의 수 N이 주어진다. (2 ≤ N ≤ 300,000)
두 번째 줄에는 각 약의 특성 Ci가 주어진다. (1 ≤ Ci ≤ N)
세 번째 줄에는 각 약의 데미지 Di가 주어진다. (1 ≤ Di ≤ 109)
약의 정보는 왼쪽으로부터 순서대로 주어진다.

24점에 해당되는 데이터는 N ≤ 15를 만족한다.
60점에 해당되는 데이터는 N ≤ 1,000을 만족한다.



첫 번째 줄에 N개의 수를 출력한다. 
i번째 수는 맨 처음에 i번째 약을 먹었을 때 수빈이가 입는 데미지의 최댓값을 의미한다.


5
1 3 3 1 3
4 3 1 2 10
5 1 10 12 1






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