同学在 $\tt{dp}$ 部分是用了优先队列以 $\mathcal{O}(n \log^2n)$ 的复杂度通过了这道题。建议添加下面数据生成器生成的数据：

#include <bits/stdc++.h>

int const L = 1e6 + 9e4;

int main() {
    std::cout << 1 << ' ' << 1 << std::endl;

    std::cout << 0 << std::endl;

    std::cout << std::string(L, '0') << std::endl;

    return 0;
}

本地可以使其跑到大约 $\tt{1.3s}$。