CF Round #889 订正
C. Dual
\(\bf \sf ez\ ver.\)
比较简单，首先不递减数组的差分数组必定是非负自然数构成的，所以我们只要全部变成正或负的，前后做一次前缀和即可。
全变成正或负，找到最大绝对值的数，对所有异号元素进行操作，理论最多次数为 \(2(n-1)=38\) 次。
\(^*\bf \sf hd\ ver.\)
我们发现异号元素可能远远大于同号元素，是否能颠倒符号。
题目中给的 \(0\le |a_i| \le 20\)，我们发现尽管是 \(1\) 和 \(-20\) 这种计算数据，只要把 \(1\) 倍增 \(\ge5\) 次就能 \(> 20\)。
现在分析一下最优次数：令同号个数为 \(a\)，异号个数为 \(b\)，且令 \(a+b=20\)。
- 当 \(b \le 12\) 时，次数为 \(b + 19\le 31\)，可以通过。
- 当 \(b > 12\) 时，则 \(a< 8\)，次数为 \(5 + a + 19 < 32\)，可以通过。
D. Earn or Unlock
把解锁代价均分到每一个牌中，则每一个前缀的代价可以提前算出，现在只要知道每个前缀是否能解锁。
然后 bitset 优化背包即可，时间复杂度 \(\mathcal O(\dfrac{n^2}{w})\)，注意转移之后要去掉扔掉的牌。