1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int hd = 1, tl, q[N];
int n;
LL A, B, C, w[N], s[N], f[N];
LL X(int x)
{
return s[x];
}
LL Y(int x)
{
return f[x] + A * s[x] * s[x] - B * s[x];
}
double slp(int a, int b)
{
return (double)(Y(a) - Y(b)) / (double)(X(a) - X(b));
}
int main()
{
scanf("%d%lld%lld%lld", &n, &A, &B, &C);
for (int i = 1; i <= n; i++)
scanf("%lld", &w[i]);
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + w[i];
q[++tl] = 0;
for (int i = 1; i <= n; i++)
{
while (hd < tl && slp(q[hd], q[hd + 1]) > 2 * A * s[i])
hd++;
int j = hd[q];
f[i] = f[j] + A * (s[i] - s[j]) * (s[i] - s[j]) + B * (s[i] - s[j]) + C;
while (hd < tl && slp(q[tl - 1], q[tl]) < slp(q[tl], i))
tl--;
q[++tl] = i;
}
printf("%lld", f[n]);
return 0;
}
|