#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 1e5 + 10, MAXX = 1e6+10;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
long long n, h[MAXN], w[MAXN];
long long pref[MAXN];
void read()
{
cin >> n;
for (long long i = 1; i <= n; ++ i)
cin >> h[i];
for (long long i = 1; i <= n; ++ i)
{
cin >> w[i];
pref[i] = pref[i-1] + w[i];
}
}
struct line
{
long long k, m;
line(){};
line(long long _k, long long _m)
{
k = _k;
m = _m;
}
long long calc(long long x)
{
return (x * k + m);
}
};
struct li_chao
{
line t[MAXX * 4];
bool used[MAXX];
void update(long long i, long long l, long long r, line curr)
{
if(l > r)return;
if(!used[i])
{
t[i] = curr;
used[i] = 1;
return;
}
if(t[i].calc(l) < curr.calc(l))swap(t[i], curr);
if(l == r)return;
long long mid = (l + r) / 2;
if(t[i].calc(mid) > curr.calc(mid))
update(i * 2 + 1, mid + 1, r, curr);
else
{
swap(t[i], curr);
update(i * 2, l, mid, curr);
}
}
long long query(long long i, long long l, long long r, long long x)
{
if(l > r)return 1e17;
if(!used[i])return 1e17;
if(l == r)return t[i].calc(x);
long long mid = (l + r) / 2, res = t[i].calc(x);
if(x <= mid)res = min(res, query(i * 2, l, mid, x));
else res = min(res, query(i * 2 + 1, mid + 1, r, x));
return res;
}
};
li_chao li;
long long dp[MAXN];
void solve()
{
dp[1] = 0;
line neww = line(- 2 * h[1], h[1] * h[1] - pref[1]);
//cout << "k = " << - 2 * h[1] << " m = " << h[1] * h[1] - pref[1] << endl;
li.update(1, 1, 1e6, neww);
for (long long i = 2; i <= n; ++ i)
{
dp[i] = li.query(1, 1, 1e6, h[i]) + h[i] * h[i] + pref[i-1];
// cout << dp[i] << endl;
neww = line(- 2*h[i], h[i] * h[i] - pref[i] + dp[i]);
// cout << "k = " << - 2 * h[i] << " m = " << h[i] * h[i] - pref[i] + dp[i] << endl;
li.update(1, 1, 1e6, neww);
}
cout << dp[n] << endl;
}
int main()
{
speed();
read();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
