g5-09055. 领班核对 · 林老师的题库

题目描述

后厨有 $n$ 个备餐时段和 $n$ 道备选菜，第 $i$ 道菜必须在第 $T_{i}$ 个时段结束前做完才有报酬 $R_{i}$ ，每个时段只做一道菜。

领班交上来一张排班表： $n$ 个数，第 $i$ 个数表示时段 $i$ 做的菜的编号， $0$ 表示该时段空闲。请核对这张排班表是否既合法又最好：

合法：每个编号至多出现一次，且出现的每道菜的时段编号不超过它的 $T_{i}$ ；
最好：排上的菜的报酬总和已经是可能的最大值。

两个条件都满足输出 YES，否则输出 NO。

输入格式

第一行一个整数 $n$ 。第二行 $n$ 个整数 $T_{1}, \dots, T_{n}$ 。第三行 $n$ 个整数 $R_{1}, \dots, R_{n}$ 。第四行 $n$ 个整数，即排班表。

输出格式

一行，YES 或 NO。

样例

输入

4
4 2 2 1
10 30 20 40
4 2 0 1

输出

YES

样例解释

样例 1：菜 $4$ 在时段 $1$ （不超过上限 $T_{4} = 1$ ）、菜 $2$ 在时段 $2$ （不超过 $T_{2} = 2$ ）、菜 $1$ 在时段 $4$ （不超过 $T_{1} = 4$ ），合法；报酬 $40 + 30 + 10 = 80$ 已是最大，YES。样例 2：菜 $4$ 放时段 $1$ 、菜 $3$ 放时段 $2$ ，各不超过上限，合法；但报酬 $40 + 20 = 60$ 小于最大值 $80$ ，不是最好，NO。

数据范围

$1 \leq n \leq 500$ ， $1 \leq T_{i} \leq n$ ， $1 \leq R_{i} \leq 1000$ ，排班表中每个数在 $0$ 到 $n$ 之间。

g5-09055. 领班核对 未做

题目描述

输入格式

输出格式

样例

样例解释

数据范围

g5-09055. 领班核对未做