#P18411. Joining Cats
Joining Cats
Joining Cats
Suzukaze Aoba 有一把魔法风扇。一条直线上从左到右坐着 n 只猫,她想知道能否通过最多 k 次启动风扇,把所有猫合并成一只。
第 i 次启动风扇会产生一阵强度恰好为 s_i的风。对于每阵风,Aoba 可以选择它的出发位置,以及向东或向西的方向。风从出发位置开始,以恒定速度沿所选方向连续移动。Aoba 可以在任意时刻关闭风扇,此时风消失。
当风遇到一只猫时:
- 如果猫的重量严格大于风的强度,风扇自动关闭。
- 否则,猫会持续被推向风吹的方向。
两只猫相遇时,会合并成一只重量等于二者重量之和的猫。上述规则随即作用于新合并的猫。因此,一次接触已经完成合并,即使新重量超过风强,也只是让风在这次合并后停止。
判断最多启动 k 次风扇,能否让所有猫合并成一只。风强必须按给定的启动顺序使用,不能自行选择或排序。
输入格式
第一行两个整数 n、k,满足1≤n,k≤5000。
第二行 n 个整数 w_1,…,w_n,表示初始从左至右各只猫的重量,1≤w_i≤1000000000。任意两只猫初始坐在不同的位置。
第三行 k 个整数 s_1,…,s_k,表示第1次至第k次启动的风强,1≤s_i≤1000000000。
输入只有一组数据。
输出格式
输出一行一个区分大小写的单词:若可以合并成一只猫,输出 Yes,否则输出 No。
样例 1
5 2
1 1 1 1 1
2 2
Yes
样例 2
6 7
3 2 1 1 2 3
2 2 2 2 2 2 2
No
样例 3
7 4
1 2 3 4 3 2 1
3 3 3 3
Yes
样例 4
5 1
5 4 3 2 1
10
Yes