你好弱啊
by Gemini7X @ 2021-01-20 23:24:13
连马老师都不如
by Gemini7X @ 2021-01-20 23:24:47
你的斜率一看就有问题
by Gemini7X @ 2021-01-20 23:25:12
那确实
by Rossie65536 @ 2021-01-20 23:25:19
你的决策点都不对建议重学斜率优化
by Gemini7X @ 2021-01-20 23:26:27
为啥换一下顺序就过了？
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 5;
int n, l;
int a[N], s[N];
int f[N], q[N], tail, head;
inline int x(int i) {
return s[i] + l;
}
inline int y(int i) {
return f[i] + (s[i] + l) * (s[i] + l);
}
inline int k(int i) {
return 2 * s[i];
}
inline long double calc(int i, int j) {
return (long double)(y(i) - y(j)) / (long double)(x(i) - x(j));
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("project.in", "r", stdin);
freopen("project.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin >> n >> l;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
for (int i = 1; i <= n; ++i) s[i] += i;
++l;
q[tail = head = 1] = 0;
for (int i = 1; i <= n; ++i) {
while (head < tail && calc(q[head + 1], q[head]) < k(i)) ++head;
f[i] = f[q[head]] + (s[i] - s[q[head]] - l) * (s[i] - s[q[head]] - l);
while (head < tail && calc(q[tail], q[tail - 1]) > calc(i, q[tail - 1])) --tail;
q[++tail] = i;
}
cout << f[n] << '\n';
return 0;
}
```
by Rossie65536 @ 2021-01-20 23:38:26