bool debug = false; #include #include using namespace std; typedef long long int ll; constexpr int kN = int(3E2 + 10); constexpr ll kInf = ll(1E16 + 10); struct From { ll A, B, lim, st; int id; From(ll a, ll b, ll c, ll d, int e){A = a, B = b, lim = c, st = d, id = e;} From(){} ll operator ()(ll x){return A * x + B;} }; int n; ll a[kN], s[kN], ans[kN], dp[kN][kN]; int main() { ll top, nxt; From tmp; deque dq; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); s[0] = 0; for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i]; for (int i = 1; i <= n; i++) dp[0][i] = 0; for (int i = 1; i <= n; i++) dp[i][0] = s[i] * s[i]; for (int i = 1; i <= n; i++) { top = 0; dq.clear(); dp[1][i] = 0; dq.push_back(From(-(s[1] << 1), s[1] * s[1], kInf, 0, 0)); for (int j = 1; j <= n; j++) { while (!dq.empty()) { if (dq[0].lim < s[j]) dq.pop_front(); else break; } dp[j][i] = dq.front()(s[j]) + s[j] * s[j]; if (debug) printf("dp[%d][%d] = %lld, dq.front() = %lld, %lld, id = %d\n", j, i, dp[j][i], dq.front().A, dq.front().B, dq.front().id); tmp = From(-(s[j + 1] << 1), dp[j][i - 1] + s[j + 1] * s[j + 1], kInf, 0, j); while (!dq.empty()) { nxt = (tmp.B - dq.back().B - 1) / (dq.back().A - tmp.A); if (dq.back().st > nxt) dq.pop_back(); else { dq.back().lim = nxt; tmp.st = nxt + 1; break; } } dq.push_back(tmp); } } for (int i = 1; i <= n; i++) printf("%lld\n", dp[n][n - i]); }