실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
서연이의 N명의 친구들 (1 <= N <= 10,000)은 1..N으로 번호가 매겨져 있으며, 파티 준비를 위해 각각 업무를 맡았습니다. 각 친구 i는 일을 완료하는 데 T(i)단위의 시간이 걸립니다. 그리고 일부 일은 다른 일이 완료되기 전에 시작될 수 없습니다. 친구 A가 친구 B보다 먼저 일을 완료해야한다면, 친구 A의 일이 완전히 완료될 때까지 친구 B의 일을 시작할 수 없습니다.
서연이는 파티 준비를 빨리 끝내기 위해 여러 명의 친구들을 동시에 일을 시킬 수 있습니다. 동시에 일을 진행할 순 있지만 일부 일이 다른 일보다 먼저 완료되어야하는 제약 조건이 있어 빨리 끝내는 데 제한이 있습니다.
서연이 전체 작업이 완료되는 데 걸리는 최소 시간을 계산하는 것을 도와주십시오.
3 1 10 5 6 3 2
11
출처: USACO 2013 February Contest, Silver Problem 3. Milk Scheduling