This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
vector<int> vect3;
struct Line {
int m, b;
int operator()(int x) { return m * x + b; }
} a[maxn*4];
void insert(int l, int r, Line seg, int o) {
if(l + 1 == r) {
if(seg(vect3[l]) > a[o](vect3[l])) a[o] = seg;
return;
}
int mid= (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;
if(a[o].m > seg.m) swap(a[o], seg);
if(a[o](vect3[mid]) < seg(vect3[mid])) {
swap(a[o], seg);
insert(l, mid, seg, lson);
}
else insert(mid, r, seg, rson);
}
int query(int l, int r, int x, int o) {
if(l + 1 == r) return a[o](vect3[x]);
int mid = (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;
if(x < mid) return max(a[o](vect3[x]), query(l, mid, x, lson));
else return max(a[o](vect3[x]), query(mid, r, x, rson));
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
for(int i=0;i<maxn*4;i++){
a[i] = {(int)0,(int)(-10000000000000000)};
}
int no_of_input;
cin >> no_of_input;
int input;
int s = 0;
vector<int> vect1;
set<int> set1;
vector<int> vect2;
vector<int> dp(no_of_input+1,0);
for(int i=0;i<no_of_input;i++){
cin >> input;
set1.insert(input);
vect1.push_back(input);
}
auto kk = set1.begin();
while(kk!=set1.end()){
vect3.push_back(*kk);
kk++;
}
for(int i=0;i<no_of_input;i++){
cin >> input;
s += input;
vect2.push_back(input);
}
dp[0] = 0;
Line temp;
temp.m = 2*vect1[0];
temp.b = -(vect1[0]*vect1[0]-vect2[0]);
insert(0,vect3.size()-1,temp,0);
for(int i=1;i<no_of_input;i++){
//cout << query(0,maxn,vect1[i],0) << endl;
int lpos = lower_bound(vect3.begin(),vect3.end(),vect1[i])-vect3.begin();
dp[i] = -query(0,vect3.size()-1,lpos,0)-vect2[i]+vect1[i]*vect1[i];
Line temp;
temp.m = 2*vect1[i];
temp.b = -(vect1[i]*vect1[i]+dp[i]);
//cout << temp.m << " " << temp.b << endl;
insert(0,vect3.size()-1,temp,0);
}
/*for(int i=0;i<no_of_input;i++){
cout << dp[i] << ' ';
}
cout << endl;*/
cout << dp[no_of_input-1]+s;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |