| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 303 | 124 | 102 | 43.220% |
휴가가 얼마 남지 않은 용범이는 휴가를 나가기 전에 밀린 업무들을 처리하려고 한다. 그러나 모든 업무를 처리하기에는 시간이 부족하기 때문에 중요한 업무들만 처리하고 나가려고 한다.
용범이가 밀린 업무는 총 $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번