#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+100;
const int MAX = 1e6+100;
const ll inf = 1e18;
struct LiChao{
struct pt{ ll m, c; };
ll eval(pt p, ll x) { return p.m * x + p.c; }
pt t[MAX<<2];
LiChao() { for(int i = 0; i < (MAX<<2); i++) t[i] = {0,inf}; }
void insert(int node, int L, int R, pt p) {
if(L == R) {
if(eval(p,L) < eval(t[node],L)) t[node] = p;
return;
} int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
bool one = eval(p,L) < eval(t[node],L);
bool two = eval(p,mid) < eval(t[node],mid);
if(one && two) {
t[node] = p;
insert(rc, mid+1, R, p);
} else if(one) insert(lc, L, mid, p);
else if(two) {
t[node] = p;
insert(lc, L, mid, p);
} else insert(rc, mid+1, R, p);
}
ll get(int node, int L, int R, ll x) {
if(L == R) return eval(t[node], x);
int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
if(x <= mid) return min(eval(t[node], x), get(lc, L, mid, x));
return min(eval(t[node], x), get(rc, mid+1, R, x));
}
}ds;
int n;
ll h[N], w[N], S[N], dp[N];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%lld", &h[i]);
for(int i = 1; i <= n; i++) {
scanf("%lld", &w[i]);
S[i] = S[i-1] + w[i];
}
dp[1] = 0;
ds.insert(1, 0, MAX-1, {-2ll*h[1], h[1]*h[1] - S[1]});
for(int i = 2; i <= n; i++) {
ll got = ds.get(1, 0, MAX-1, h[i]);
dp[i] = got + h[i] * h[i] + S[i-1];
ds.insert(1, 0, MAX-1, {-2ll*h[i], dp[i] - S[i] + h[i] * h[i]});
}
printf("%lld\n", dp[n]);
return 0;
}
Compilation message
building.cpp: In function 'int main()':
building.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
building.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &h[i]);
~~~~~^~~~~~~~~~~~~~~
building.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &w[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
62968 KB |
Output is correct |
| 2 |
Incorrect |
49 ms |
62968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
67152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
62968 KB |
Output is correct |
| 2 |
Incorrect |
49 ms |
62968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
