有点狗，但还算个好题。
设定 $f_i(x)=a_ix-x^3$，$\Delta_i(x)=f_i(x)-f_i(x-1)$，可以洞察到 $\Delta_i(x)$ 在正自然数中是递减的。那么我们就可以贪心了。贪心时我们维护一个向量 $(b_1,\dots,b_n)$，分别表示 $\Delta_i(b_i)$，初始全为零。放进优先队列里面，每次取一个出来（记为 $\textit{id}$）将 $b_{\textit{id}}$ 增量 $1$，再放入优先队列里面。最终我们得到的即是使得答案最优的向量。
复杂度不可接受，我们优化的方向应当是提高生产力，怎样批量决定该做哪些。考虑二分一个标准线 $t$，如果存在向量满足 $\sum b_i\leqslant k$，且我们只做了 $\Delta_i(b_i)\geqslant t$ 的函数，就行了。设 $f(t)$ 为达到标准线的函数个数，最后我们得到的 $t$ 满足 $f(t)\leqslant k<f(t+1)$。
然后通过调整可得到答案。
#include <bits/stdc++.h>
using namespace std;
using ll = __int128;
#define int ll
int n, k, a[100100], b[100100];
ll of(ll x, ll a) {
return a*x-x*x*x;
}
ll df(ll x, ll i) {
return of(x, a[i])-of(x-1, a[i]);
}
int f(int i, int stl) {
int l = 0, r = a[i], mid, res = 0;
while (l <= r) {
mid = (l+r)/2;
if (df(mid, i) >= stl) l = mid+1, res = mid;
else r = mid-1;
}
return res;
}
bool check(ll cur) {
// @cur stands for the standard line
ll sm = 0;
for (int i=1;i<=n;++i) {
int ret = f(i, cur);
sm += ret, b[i] = ret;
}
return sm <= k;
}
ll bsrh(ll l, ll r) {
ll mid, res = -1;
while (l <= r) {
if(check(mid = (l+r)/2)) r = mid-1, res = mid;
else l = mid+1;
}
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
long long tmp;
cin >> tmp;
n = tmp;
cin >> tmp;
k = tmp;
for (int i=1;i<=n;++i) {
cin >> tmp;
a[i] = tmp;
}
int t = bsrh(-9e18, 9e18), sum = 0;
check(t-1);
for (int i=1;i<=n;++i) sum += b[i];
for (int i=1;i<=n;++i) {
int adj = f(i, t-1)-f(i, t);
if (sum > k) {
if (sum-adj <= k) {
b[i] -= (sum-k);
break;
}
else {
sum -= adj, b[i] -= adj;
}
}
}
for (int i=1;i<=n;++i) {
tmp = b[i];
cout << tmp << " \n"[i == n];
}
return 0;
}