| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 285 | 113 | 92 | 42.009% |
휴가가 얼마 남지 않은 용범이는 휴가를 나가기 전에 밀린 업무들을 처리하려고 한다. 그러나 모든 업무를 처리하기에는 시간이 부족하기 때문에 중요한 업무들만 처리하고 나가려고 한다.
용범이가 밀린 업무는 총 $N$개가 있고, 1ドル$번부터 $N$번까지 업무마다 번호가 매겨져 있다. 또한, 각 업무는 해당 업무를 처리하기 전에 먼저 처리해야 하는 선행 업무가 최대 1ドル$개 있을 수 있으며, 각 업무들의 선행 업무는 모두 다르다. 용범이는 한 번에 한 업무만 처리할 수 있기 때문에, 업무마다 중요도 $w_i$와 처리하는 데 걸리는 시간 $t_i$를 정리하고 어떻게 업무를 처리하는 것이 효율적인지 알아내려고 한다. 업무들을 처리하는 데 걸리는 시간은 처리한 업무들의 처리 시간의 합이다.
충분한 시간이 주어진다면 용범이는 모든 업무를 처리할 수 있지만, 휴가를 나가기까지 시간이 얼마 남지 않았다. 빨리 휴가를 나가고 싶어하는 용범이를 도와 처리한 업무들의 중요도 합이 $S$ 이상이 되게 하는데 필요한 최소 시간을 구해주자.
첫 번째 줄에 업무의 수 $N$과 처리한 업무들의 중요도 합의 최소 $S$가 공백으로 구분되어 정수로 주어진다. $(1 \le N \le 1,000円;$ 1ドル \le S \le 100,000円)$
두 번째 줄에 각 업무의 중요도 $w_1,w_2,\cdots,w_N$이 공백으로 구분되어 정수로 주어진다. $(1 \le w_i \le 100)$
세 번째 줄에 각 업무의 처리 시간 $t_1,t_2,\cdots,t_N$이 공백으로 구분되어 정수로 주어진다. $(1 \le t_i \le 1,000円)$
네 번째 줄에 각 업무의 선행 업무 번호 $p_1,p_2,\cdots,p_N$이 공백으로 구분되어 정수로 주어진다.선행 업무의 번호가 0ドル$이면 선행 업무가 없는 것이다. 0ドル$이 아닌 모든 $p_i$들은 서로 다르다. $(0 \le p_i \le N)$
충분한 시간이 주어진다면 모든 업무를 처리할 수 있는 경우만 입력으로 주어진다.
처리한 업무의 중요도의 합이 $S$이상이 되게 하는데 필요한 시간의 최솟값을 출력한다. 만약 모든 업무를 처리해도 중요도의 합이 $S$ 미만이라면 $-1$을 출력한다.
7 7 2 3 1 4 5 1 3 3 4 2 8 6 1 2 0 1 2 0 4 0 0
9
1ドル$번 2ドル$번 7ドル$번 업무를 처리하면 중요도의 합은 8ドル$이 되고 처리 시간은 9ドル$로 최소가 된다. 중요도의 합이 7ドル$이 되게 업무를 처리하려면 1ドル$ ,2ドル,ドル 3ドル,ドル 6ドル$번 업무를 처리하면 되고 처리 시간의 합은 10ドル$이므로 최소가 아니다.
5 13 2 5 3 1 1 4 2 5 6 3 0 1 2 0 4
-1
모든 업무를 처리해도 중요도의 합이 12ドル$이다.
Contest > 보라매컵 > 제2회 보라매컵 본선 D번