#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>
const int N = 4e6+10;
const int M = 2e5+10;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;
struct Line{
LL a ,b;
LL get_val(LL x){return a*x+b;}
Line(){
a = -INF;
b = -INF;
}
Line(LL a1,LL b1){
a = a1;
b = b1;
}
};
struct node{
node *l,*r;
Line line;
node(Line L):line(L),l(NULL),r(NULL){};
};
LL a[M],pr[M],dp[M];
Line tree[N];
void update(int v,int tl,int tr,Line l){
int mid = (tl+tr)/2;
bool L = tree[v].get_val(tl) > l.get_val(tl);
bool R = tree[v].get_val(tr) > l.get_val(tr);
bool M = tree[v].get_val(mid) > l.get_val(mid);
if(L==R){
if(!L)swap(l,tree[v]);
return ;
}
if(M==R){
if(!R)swap(tree[v],l);
update(v*2,tl,mid,l);
}
else {
if(!L)swap(tree[v],l);
update(v*2+1,mid+1,tr,l);
}
return ;
}
LL get(int v,int tl,int tr,int pos){
if(tl==tr)
return tree[v].get_val(pos);
int mid = (tl+tr)/2;
if(pos<=mid)
return max(tree[v].get_val(pos),get(v*2,tl,mid,pos));
else
return max(tree[v].get_val(pos),get(v*2+1,mid+1,tr,pos));
}
int main(){
//freopen("out.txt","w",stdout);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)
scanf("%lld",&pr[i]),pr[i] += pr[i-1];
Line l = Line(2*a[1],-pr[1]-a[1]*a[1]);
update(1,0,1e6,l);
for(int i=2;i<=n;i++){
dp[i] = a[i]*a[i]+pr[i-1]-get(1,0,1e6,a[i]);
l = Line(2*a[i],+pr[i]-a[i]*a[i]-dp[i]);
update(1,0,1e6,l);
}
printf("%lld\n",dp[n]);
}
Compilation message
building.cpp: In constructor 'node::node(Line)':
building.cpp:35:10: warning: 'node::line' will be initialized after [-Wreorder]
35 | Line line;
| ^~~~
building.cpp:34:11: warning: 'node* node::l' [-Wreorder]
34 | node *l,*r;
| ^
building.cpp:37:5: warning: when initialized here [-Wreorder]
37 | node(Line L):line(L),l(NULL),r(NULL){};
| ^~~~
building.cpp: In function 'int main()':
building.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
building.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%lld",&a[i]);
| ~~~~~^~~~~~~~~~~~~~
building.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%lld",&pr[i]),pr[i] += pr[i-1];
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
62900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
66284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
62900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
