#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
vector<int> vect3;
struct line{
int m,c;
int operator()(int x){
return m*x+c;
}
}a[maxn*4];
void insert(int node,int start,int end,line l){
if(start==end){
if(a[node](vect3[start])<l(vect3[start])){
a[node] = l;
}
return;
}
if(a[node].m>l.m){
swap(a[node],l);
}
int mid = (start+end)/2;
if(a[node](vect3[mid])<l(vect3[mid])){
swap(a[node],l);
insert(node*2+1,start,mid,l);
}
else{
insert(node*2+2,mid+1,end,l);
}
}
int query(int node,int start,int end,int pos){
if(start==end){
return a[node](vect3[pos]);
}
int mid = (start+end)/2;
if(pos<=mid){
return max(a[node](vect3[pos]),query(node*2+1,start,mid,pos));
}
else{
return max(a[node](vect3[pos]),query(node*2+2,mid+1,end,pos));
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int no_of_input;
vector<int> vect1;
vector<int> vect2;
vector<int> dp(maxn);
int input;
cin >> no_of_input;
for(int i=0;i<no_of_input;i++){
cin >> input;
vect1.push_back(input);
}
for(int i=0;i<no_of_input;i++){
cin >> input;
vect2.push_back(input);
}
vect3 = vect1;
sort(vect3.begin(),vect3.end());
for(int i=0;i<maxn*4;i++){
a[i] = {0,-INT_MAX};
}
insert(0,0,vect3.size()-1,{2*vect1[0],-vect1[0]*vect1[0]});
for(int i=1;i<no_of_input;i++){
int pos = lower_bound(vect3.begin(),vect3.end(),vect1[i])-vect3.begin();
int mini = query(0,0,vect3.size()-1,pos);
dp[i] = -mini+vect1[i]*vect1[i]-vect2[i];
insert(0,0,vect3.size()-1,{2*vect1[i],-(dp[i]+vect1[i]*vect1[i])});
}
int sum = 0;
for(auto k:vect2){
sum += k;
}
cout << dp[no_of_input-1]+sum;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
9848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
