序列加法机

首先模拟数据得到均分是最优的，而不是每一次对半。

然后用得出 cost(i, j) 表示把第 $i$ 个位置划分成 $j$ 个位置

令 $v = a_i$，$q = \lfloor \frac v j \rfloor$，$r = v \mod j$

cost(i, j) $= (j-r) \times q ^ 2 + r \times {(q+1)}^2$

然后按照 $cost(i, cnt_i) - cost(i, cnt_i+1)$ 降序排序

然后每一次取出一个节点 $x$ 并执行 $cnt_x \leftarrow cnt_x + 1$

注意点：

1. cost 可能较大，但单个 cost 不能取模，需要使用 __int128_t
2. 注意当 $cnt_x < a_x$ 的时候才能入优先队列，否则不能进入优先队列

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T, class U>
inline bool chmax(T& a, const U& b)
{
    return a < b ? a = b, true : false;
}
template<class T, class U>
inline bool chmin(T& a, const U& b)
{
    return a > b ? a = b, true : false;
}
constexpr size_t N = 100005;
constexpr int MOD = 998244353;
int n, m;
int a[N];
int idx[N];
int cnt[N];
__int128 cost(int d, int k)
{
    d = a[d];
    ll q = d / k, r = d % k;
    return (k - r) * q * __int128(q) + r * (q + 1) * __int128(q + 1);
}
bool cmp(int a, int b)
{
    return cost(a, cnt[a]) - cost(a, cnt[a] + 1) < cost(b, cnt[b]) - cost(b, cnt[b] + 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        cnt[i] = 1;
    }
    int x;
    int s = 0;
    ll res = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        a[i] = abs(a[i] - x);
        idx[i] = i;
        if (a[i] == 1)
        {
            res++;
            m--;
            continue;
        }
        if (a[i] != 0)
        {
            a[++s] = a[i];
        }
    }
    if (m < s)
    {
        cout << "-1\n";
        return 0;
    }
    m -= s;
    make_heap(idx + 1, idx + s + 1, cmp);
    while (m-- && s > 0)
    {
        x = idx[1];
        pop_heap(idx + 1, idx + s + 1, cmp);
        cnt[x]++;
        if (cnt[x] < a[x])
        {
            push_heap(idx + 1, idx + s + 1, cmp);
        }
        else
        {
            res += cost(x, cnt[x]) % MOD;
            res %= MOD;
            s--;
        }
    }
    for (int i = 1; i <= s; i++)
    {
        res = (res + cost(idx[i], cnt[idx[i]])) % MOD;
    }
    cout << res << '\n';
    return 0;
}