第一个想法显然是二分答案，可以考虑二分 \(C\) 值后枚举每一个权值区间进行判定，时间复杂度为 \(O(nk^2\min(a,nk)\log a)\)。这个已经有 \(5\times(5+4+5)=70\) 分了？？写一下。好吧假假假，每个权值区间毙掉的每个位置的密码锁状态都不同，并不好直接处理。很好现在 \(25\) 分。
可以设 dp，对于每一维我们会关心最小值和最大值，最暴力的 dp 是 \(2k\) 维度的，现在大概有 \(40\) 分了，不过这分有点难泵。
按 \(k\) 讨论的话，\(k=1\) 显然可以直接算，\(k=2\) 的时候贪心地讲，我们会把每个转锁的较小值放一边，较大值放另一边，然后可以直接统计。诶诶，现在有 \(30+10+10=50\) 分了。
\(k=3,4\) 怎么做呃呃呃。
考虑我们一定不会把全局的最大值最小值转到同一行，否则 \(C\) 就为全局极差。同理，如果固定最大值的所在行，我们也会尽量使得次小值与它不在同一行。扩展地来讲，我们会使得被迫与其在同一行的元素的最小值尽可能地大。
先考虑 \(k=3\) 的情况。此时最大值和最小值会占两行，然后二分答案判定第三行即可。
但是麻烦麻烦麻烦，考虑随机重排序列后贪心，过了。
随机化算法！！！！