/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef long long ftyp;
typedef std::complex<ftyp> vec;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define cx real
#define cy imag
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e9+7;
const ll sus = 1e6 + 5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll a , ll b){
return (rng() % (b-a+1)) + a;
}
/*global variables*/
ll n;
std::vector<ll> ar , br;
std::vector<vec> valt;
/**/
/*functions*/
ftyp dot(vec a , vec b){
return (std::conj(a) * b).cy();
}
void addLine(vec dd , ftyp l , ftyp r , ll a){
ll md = (l + r + 1)/2;
ll fo = dot(dd , {l , 1}) < dot(valt[a] , {l , 1}) , so = dot(dd , {md , 1}) < dot(valt[a] , {md , 1});
//std::cout << l << " " << r << " " << dd.cx() << " " << dd.cy() << "\n";
if(so){
std::swap(valt[a] , dd);
}
if(l >= r){
return;
}
if(fo != so){
addLine(dd , l , md-1 , a*2);
}
else{
addLine(dd , md , r , a*2+1);
}
}
ftyp gt(ll x , ll l , ll r , ll a){
ll md = (l + r + 1)/2;
if(l >= r){
/*std::cout << valt[a].cx() << " " << valt[a].cy() << "\n";
std::cout << dot(valt[a] , {x , 1}) << "\n";*/
return dot(valt[a] , {x , 1});
}
else if(md > x){
return std::min(dot(valt[a] , {x , 1}) , gt(x , l , md-1 , a*2));
}
else{
return std::min(dot(valt[a] , {x , 1}) , gt(x , md , r , a*2+1));
}
}
/**/
void solve(){
std::cin >> n;
ar.resize(n);
br.resize(n);
for(ll i = 0 ; n>i;i++){
std::cin >> ar[i];
}
ll sm = 0;
for(ll i = 0 ; n>i;i++){
std::cin >> br[i];
sm+=br[i];
}
valt.resize(sus*4 , {(ar[0] * ar[0]) - br[0] , 2 * ar[0]});
ll ans = 0;
for(ll i = 1;n>i;i++){
ll a = gt(ar[i] , 0 , sus , 1);
ans = ar[i] * ar[i] + a - br[i];
addLine({ans + ar[i] * ar[i] , 2 * ar[i]} , 0 , sus , 1);
/*std::cout << a << "\n";
std::cout << ans << "\n";
std::cout << std::endl;*/
}
std::cout << ans + sm;
return;/**/
}
int main(){
std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
/*#ifndef ONLINE_JUDGE
freopen("in.txt" , "r" , stdin);
freopen("out.txt" , "w" , stdout);
#endif*/
ll t = 1;
//std::cin >> t;
while(t--){
solve();
}
}
Compilation message
building.cpp:5:78: warning: "/*" within comment [-Wcomment]
5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
|
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
62932 KB |
Output is correct |
2 |
Correct |
25 ms |
62884 KB |
Output is correct |
3 |
Correct |
24 ms |
62932 KB |
Output is correct |
4 |
Correct |
25 ms |
62932 KB |
Output is correct |
5 |
Correct |
25 ms |
62924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
65480 KB |
Output is correct |
2 |
Correct |
64 ms |
65428 KB |
Output is correct |
3 |
Correct |
66 ms |
65544 KB |
Output is correct |
4 |
Correct |
60 ms |
65456 KB |
Output is correct |
5 |
Correct |
57 ms |
65340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
62932 KB |
Output is correct |
2 |
Correct |
25 ms |
62884 KB |
Output is correct |
3 |
Correct |
24 ms |
62932 KB |
Output is correct |
4 |
Correct |
25 ms |
62932 KB |
Output is correct |
5 |
Correct |
25 ms |
62924 KB |
Output is correct |
6 |
Correct |
69 ms |
65480 KB |
Output is correct |
7 |
Correct |
64 ms |
65428 KB |
Output is correct |
8 |
Correct |
66 ms |
65544 KB |
Output is correct |
9 |
Correct |
60 ms |
65456 KB |
Output is correct |
10 |
Correct |
57 ms |
65340 KB |
Output is correct |
11 |
Correct |
78 ms |
65612 KB |
Output is correct |
12 |
Correct |
71 ms |
65436 KB |
Output is correct |
13 |
Correct |
59 ms |
65596 KB |
Output is correct |
14 |
Correct |
74 ms |
65628 KB |
Output is correct |
15 |
Correct |
58 ms |
65356 KB |
Output is correct |
16 |
Correct |
65 ms |
65368 KB |
Output is correct |
17 |
Correct |
53 ms |
65496 KB |
Output is correct |
18 |
Correct |
53 ms |
65612 KB |
Output is correct |