#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
struct func {
ll k, b;
func(ll k = 0, ll b = 1e18) :k(k), b(b){
}
ll operator()(ll x) {
return k*x+b;
}
};
const int maxn = 1e6 + 55;
func tree[4*maxn];
void upd(int v, int l, int r, func f) {
// cout << v << " " << l << " " << r << "\n";
int m = (l+r)>>1;
int L = f(l) < tree[v](l);
int M = f(m) < tree[v](m);
if(M) {
swap(f, tree[v]);
}
if(r-l<2) return;
if(L!=M)
upd(v<<1, l, m, f);
else
upd(v<<1|1, m, r, f);
}
ll get(int v, int l, int r, int x) {
ll m = (l+r)>>1;
if(r-l<2) return tree[v](x);
if(v<m)
return min(tree[v](x), get(v<<1, l, m, x));
else
return min(tree[v](x), get(v<<1|1, m, r, x));
}
void add(func f) {
upd(1, 0, 1e6 + 1, f);
}
ll get(ll x) {
return get(1, 0, 1e6 + 1, x);
}
ll n, h[maxn], w[maxn], pref[maxn];
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = 1; i <= n; i++) {
cin >> w[i];
pref[i] = pref[i-1]+w[i];
}
ll t = 0;
add(func(-2*h[1], h[1]*h[1]-pref[1]));
// return 0;
for(int i = 2; i <= n; i++) {
t = get(h[i]) + h[i]*h[i] + pref[i-1];
add(func(-2*h[i], t + h[i]*h[i] - pref[i]));
}
cout << t;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
62968 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
62968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
163 ms |
66424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
62968 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
62968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
