#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <bits/stdc++.h>
#define fu(i, a, b) for(int i = (a); i <= (b); i++)
#define fd(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define bit(mask, x) (mask & (1LL << x))
#define pi pair<int, int>
#define pl pair<ll, ll>
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define nl cout << '\n';
#define pb push_back
using namespace std;
//#define double long double
const int N = (int)1e5 + 5;
int dx[8] = {0, 0, -1, 1, -1, -1, 1, 1};
int dy[8] = {1, -1, 0, 0, -1, 1, -1, 1};
const ll INF = (ll)1e9 + 5;
const ll MOD = (ll)998244353;
const int LOG = 30;
const ll cow = 37;
const double eps = 0.0001;
const int M =(int)2e6 + 5;
template<class T1>
void print(T1 a) {cout << a << ' ';}
template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2>
void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}
template<class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}
template<class T1, class T2>
void mul(T1 &a, T2 b) {a *= b; a%=MOD; return a;}
template<typename T, typename V>
void print(pair<T, V> &p) {print(p.fi); print(p.se);}
template<typename T>
void print(vector<T> v) {for (int i = 0; i < (int)v.size(); i++) print(v[i]);}
template<typename T>
void print(vector<vector<T>> v) {
for (int i = 0; i < v.size(); i++){
for (int j = 0; j < v[i].size(); j++)
print(v[i][j]);
nl;
}
}
template<typename T>
int sz(T x) {return (int)x.size();}
struct line
{
ll a, b, c;
line(ll _a = 0, ll _b = 0)
{
a = _a;
b = _b;
}
ll get_val(ll x)
{
return a * x + b;
}
};
vector<line> st;
int n;
ll h[N], w[N];
ll pref[N], dp[N];
bool so_sanh(line l1, line l2, line l3)
{
ll p1 = (l1.a - l3.a) * (l2.b - l1.b);
ll p2 = (l1.a - l2.a) * (l3.b - l1.b);
return p1 > p2;
}
bool so_sanh2(line l1, line l2, line l3)
{
ll p1 = (l1.a - l3.a) * (l2.b - l1.b);
ll p2 = (l1.a - l2.a) * (l3.b - l1.b);
return p1 > p2;
}
void addline(line a, int type)
{
while(st.size() >= 2)
{
if((type == 1 && so_sanh(st[(int)st.size() - 2], st.back(), a)) || (type == 2 && so_sanh2(st[(int)st.size() - 2], st.back(), a))) st.pop_back();
else break;
}
st.push_back(a);
}
ll querry_max(ll a)
{
int l = 1, r = (int)st.size() - 1;
int res = 0;
while(l <= r)
{
int mid = (l + r) / 2;
if(st[mid - 1].get_val(a) <= st[mid].get_val(a)) res = mid, l = mid + 1;
else r = mid - 1;
}
ll val = 0;
if((int)st.size() >= 1) val = st[0].get_val(a);
return max(val, st[res].get_val(a));
}
ll querry_min(ll a)
{
int l = 0, r = (int)st.size() - 1;
int res = 0;
while(l <= r)
{
int mid = (l + r) / 2;
if(st[mid].get_val(a) <= st[mid + 1].get_val(a)) res = mid, r = mid - 1;
else l = mid + 1;
}
return st[res].get_val(a);
}
int main()
{// freopen("tbrackets.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
t = 1;
while(t--)
{
cin >> n;
fu(i, 1, n) cin >> h[i];
fu(i, 1, n) cin >> w[i];
fu(i, 1, n) pref[i] = pref[i - 1] + w[i];
addline(line(h[1], h[1] * h[1] - pref[1]), 1);
dp[1] = 0;
fu(i, 2, n)
{
ll val = querry_min(-2 * h[i]);
dp[i] = val + h[i] * h[i] + pref[i - 1];
addline(line{h[i], dp[i] + h[i] * h[i] - pref[i]}, 1);
}
cout << dp[n];
}
}
//7
//)()[](}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
5160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
