#include <stdio.h>
#define N 100000
#define INF 0x3f3f3f3f3f3f3f3fLL
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
long long xx[N], yy[N];
long long cross2(long long x1, long long y1, long long x2, long long y2) {
return x1 * y2 - x2 * y1;
}
long long cross(int i, int j, int k) {
return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}
int zz[1 + N * 2], ll[1 + N * 2], rr[1 + N * 2], ii[1 + N * 2], jj[1 + N * 2], u_, l_, r_;
int node(int i, int j) {
static int _ = 1;
zz[_] = rand_();
ii[_] = i, jj[_] = j;
return _++;
}
void split_x(int u, int i) {
if (u == 0) {
l_ = r_ = 0;
return;
}
if (xx[ii[u]] < xx[i] || xx[ii[u]] == xx[i] && yy[ii[u]] <= yy[i]) {
split_x(rr[u], i);
rr[u] = l_, l_ = u;
} else {
split_x(ll[u], i);
ll[u] = r_, r_ = u;
}
}
int mode;
int compare(int i, int j, int k) {
return (mode == 0) == (cross(i, j, k) > 0) ? -1 : 1;
}
void split_c(int u, int i) {
if (u == 0) {
l_ = r_ = 0;
return;
}
if (compare(ii[u], jj[u], i) < 0) {
split_c(rr[u], i);
rr[u] = l_, l_ = u;
} else {
split_c(ll[u], i);
ll[u] = r_, r_ = u;
}
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v);
return u;
} else {
ll[v] = merge(u, ll[v]);
return v;
}
}
int first(int u) { return ll[u] == 0 ? u : first(ll[u]); }
int last(int u) { return rr[u] == 0 ? u : last(rr[u]); }
int il, ir;
void update(int i) {
if (il == -1)
il = ir = i;
else if (xx[il] > xx[i] || xx[il] == xx[i] && yy[il] > yy[i]) {
mode = 1, split_c(u_, i), u_ = merge(node(i, r_ ? ii[first(r_)] : ir), r_);
il = i;
} else if (xx[ir] < xx[i] || xx[ir] == xx[i] && yy[ir] < yy[i]) {
mode = 0, split_c(u_, i), u_ = merge(l_, node(l_ ? jj[last(l_)] : il, i));
ir = i;
} else {
int u, l, r;
if (il == ir)
return;
split_x(u_, i);
l = l_, r = r_, u = last(l);
if (cross(ii[u], jj[u], i) < 0) {
mode = 0, split_c(l, i), l = merge(l_, node(l_ ? jj[last(l_)] : il, i));
mode = 1, split_c(r, i), r = merge(node(i, r_ ? ii[first(r_)] : ir), r_);
}
u_ = merge(l, r);
}
}
long long eval(int i, int x, int y) {
return xx[i] * x + yy[i] * y;
}
long long query(int x, int y) {
int u;
long long z;
if (il == ir)
return eval(il, x, y);
u = u_, z = -INF;
while (u) {
long long zi = eval(ii[u], x, y), zj = eval(jj[u], x, y);
z = max(z, max(zi, zj));
u = zi > zj ? ll[u] : rr[u];
}
return z;
}
int main() {
static int hh[N];
static long long ww[N], dp[N];
int n, i;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &hh[i]);
for (i = 0; i < n; i++)
scanf("%lld", &ww[i]);
for (i = 1; i < n; i++)
ww[i] += ww[i - 1];
il = ir = -1;
dp[0] = 0;
xx[0] = hh[0] * 2, yy[0] = dp[0] + (long long) hh[0] * hh[0] - ww[0], update(0);
for (i = 1; i < n; i++) {
dp[i] = -query(hh[i], -1) + (long long) hh[i] * hh[i] + ww[i - 1];
xx[i] = hh[i] * 2, yy[i] = dp[i] + (long long) hh[i] * hh[i] - ww[i], update(i);
}
printf("%lld\n", dp[n - 1]);
return 0;
}
Compilation message
building.c: In function 'split_x':
building.c:39:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
39 | if (xx[ii[u]] < xx[i] || xx[ii[u]] == xx[i] && yy[ii[u]] <= yy[i]) {
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
building.c: In function 'update':
building.c:90:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
90 | else if (xx[il] > xx[i] || xx[il] == xx[i] && yy[il] > yy[i]) {
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
building.c:93:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
93 | } else if (xx[ir] < xx[i] || xx[ir] == xx[i] && yy[ir] < yy[i]) {
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
building.c: In function 'main':
building.c:136:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
136 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
building.c:138:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | scanf("%d", &hh[i]);
| ^~~~~~~~~~~~~~~~~~~
building.c:140:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
140 | scanf("%lld", &ww[i]);
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
292 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
296 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
8432 KB |
Output is correct |
| 2 |
Correct |
89 ms |
8392 KB |
Output is correct |
| 3 |
Correct |
92 ms |
8372 KB |
Output is correct |
| 4 |
Correct |
83 ms |
8656 KB |
Output is correct |
| 5 |
Correct |
80 ms |
8624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
292 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
296 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
91 ms |
8432 KB |
Output is correct |
| 7 |
Correct |
89 ms |
8392 KB |
Output is correct |
| 8 |
Correct |
92 ms |
8372 KB |
Output is correct |
| 9 |
Correct |
83 ms |
8656 KB |
Output is correct |
| 10 |
Correct |
80 ms |
8624 KB |
Output is correct |
| 11 |
Correct |
81 ms |
7868 KB |
Output is correct |
| 12 |
Correct |
91 ms |
8608 KB |
Output is correct |
| 13 |
Correct |
49 ms |
7628 KB |
Output is correct |
| 14 |
Correct |
94 ms |
8312 KB |
Output is correct |
| 15 |
Correct |
57 ms |
6540 KB |
Output is correct |
| 16 |
Correct |
75 ms |
8524 KB |
Output is correct |
| 17 |
Correct |
26 ms |
4792 KB |
Output is correct |
| 18 |
Correct |
28 ms |
4828 KB |
Output is correct |
