/*==============================================================================================================
__ __ _____ ______ _______
| | | | / __ \ / _____| / ______|
__| |__ __| |__ |_| | | | | | |
|__| __| |__| __| | | | |____ | |_____
| | _____ _ | | ____ __ __ ____ _____ _____ / / \ ___ \ | ___ \
| | / _ \ | | | | / _/ | | | | / _ \ / __ \ / _ \ / / | | | | | |
| |_ | |_| | | | | |_ | | | |_| | | |_| | | | | | | |_| | / /___ ____| | | |___| |
\____\ \____/| |_| \____\ |_| \_____/ \_____/ |_| |_| \____ | |______| |______/ \_______/
| |
__/ |
|___/
Pratice, practice, and practice
Where is the bug, delete it there
Try, try, try again until you succeed
I hated every minute of training, but I said, 'Don't quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali
You may not be the best, but must be the most effort
Even the things and people you like, you don't have the courage to take, you are destined to be a failure.
Difficult means more time
Pain + Reflection = Progress
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
const ll mod = 1e9+7;
struct LiChao_tree //offline + get min
{
struct line
{
ll a, b;
ll get(ll x) {return a*x+b;}
};
ll n;
vector<line> tree;
vector<ll> compress;
LiChao_tree(vector<ll> _compress_x)
{
n=_compress_x.size()+5;
compress=_compress_x;
sort(compress.begin(), compress.end());
compress.resize(unique(compress.begin(), compress.end())-compress.begin());
tree.resize(4*n+5, {0, LLONG_MAX}); //LLONG_MIN
}
ll getid(ll val) {return lower_bound(compress.begin(), compress.end(), val)-compress.begin();}
void insert(ll id, ll l, ll r, line newL)
{
if (l==r)
{
if (newL.get(compress[l])<tree[id].get(compress[l])) tree[id]=newL; //thay dau >
return;
}
ll m=(l+r)/2;
bool lef=newL.get(compress[l])<tree[id].get(compress[l]); //thay dau >
bool mid=newL.get(compress[m])<tree[id].get(compress[m]); //thay dau >
if (mid==true) swap(newL, tree[id]);
if (lef!=mid) insert(id*2, l, m, newL);
else insert(id*2+1, m+1, r, newL);
}
void insert(ll a, ll b)
{
line newL={a, b};
insert(1, 0, n-1, newL);
}
ll query(ll id, ll l, ll r, ll x)
{
if (l==r) return tree[id].get(compress[x]);
ll m=(l+r)/2;
if (x<=m) return min(tree[id].get(compress[x]), query(id*2, l, m, x)); //max()
return min(tree[id].get(compress[x]), query(id*2+1, m+1, r, x)); //max()
}
ll query(ll x)
{
ll pos=getid(x);
return query(1, 0, n-1, pos);
}
};
ll n, tot, h[100005], w[100005], dp[100005];
void solve()
{
cin>>n;
for (ll i=1; i<=n; i++) cin>>h[i];
for (ll i=1; i<=n; i++) cin>>w[i];
vector<ll> v;
for (ll i=1; i<=n; i++) v.push_back(h[i]), tot+=w[i];
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end())-v.begin());
LiChao_tree seg(v);
dp[1]=-w[1];
for (ll i=2; i<=n; i++)
{
seg.insert(-2*h[i-1], dp[i-1]+h[i-1]*h[i-1]);
dp[i]=seg.query(h[i])-w[i]+h[i]*h[i];
}
cout<<tot+dp[n];
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
clock_t start = clock();
//#ifndef ONLINE_JUDGE
//freopen("_input.txt", "r", stdin);
//freopen("_output.txt", "w", stdout);
//#endif
solve();
clock_t end = clock();
cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
3956 KB |
Output is correct |
| 2 |
Correct |
49 ms |
5064 KB |
Output is correct |
| 3 |
Correct |
43 ms |
5064 KB |
Output is correct |
| 4 |
Correct |
36 ms |
4516 KB |
Output is correct |
| 5 |
Correct |
36 ms |
11472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
412 KB |
Output is correct |
| 6 |
Correct |
43 ms |
3956 KB |
Output is correct |
| 7 |
Correct |
49 ms |
5064 KB |
Output is correct |
| 8 |
Correct |
43 ms |
5064 KB |
Output is correct |
| 9 |
Correct |
36 ms |
4516 KB |
Output is correct |
| 10 |
Correct |
36 ms |
11472 KB |
Output is correct |
| 11 |
Correct |
59 ms |
9540 KB |
Output is correct |
| 12 |
Correct |
55 ms |
9388 KB |
Output is correct |
| 13 |
Correct |
34 ms |
4680 KB |
Output is correct |
| 14 |
Correct |
55 ms |
9496 KB |
Output is correct |
| 15 |
Correct |
37 ms |
11472 KB |
Output is correct |
| 16 |
Correct |
40 ms |
11604 KB |
Output is correct |
| 17 |
Correct |
16 ms |
4560 KB |
Output is correct |
| 18 |
Correct |
14 ms |
4560 KB |
Output is correct |
