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
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(l) > a[o](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](mid) < seg(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](x);
int mid = (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;
if(x < mid) return max(a[o](x), query(l, mid, x, lson));
else return max(a[o](x), query(mid, r, x, rson));
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int no_of_input;
cin >> no_of_input;
int input;
int s = 0;
vector<int> vect1;
vector<int> vect2;
vector<int> dp(no_of_input+1,0);
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;
s += input;
vect2.push_back(input);
}
Line temp;
temp.m = 2*vect1[0];
temp.b = -(vect1[0]*vect1[0]-vect2[0]);
insert(0,maxn,temp,0);
for(int i=1;i<no_of_input;i++){
//cout << query(0,maxn,vect1[i],0) << endl;
dp[i] = -query(0,maxn,vect1[i],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,maxn,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... |