#include <bits/stdc++.h>
using namespace std;
#define int long long
deque<pair<int,int> > lines;//lines in form of first*a+b
vector<int> sum;
int no_of_input,a,b,c;
int countt = 0;
double intersection(pair<int,int> a,pair<int,int> b){
return 1.0*(double)(((double)a.second-(double)b.second)/((double)b.first-(double)a.first));
}
void update(int a,int b){
pair<int,int> temp = {a,b};
while(lines.size()>=2&&intersection(lines[lines.size()-2],lines[lines.size()-1])>intersection(lines[lines.size()-1],temp)){
lines.pop_back();
}
lines.push_front(temp);
/*cout << "--\n";
for(auto k:lines){
cout << k.first << " " << k.second << endl;
}
cout << "--\n";*/
return;
}
int query(int pos){
int res = 0;
for(int i=0;i<lines.size();i++){
res = max(res,lines[i].first*pos+lines[i].second);
}
return res;
int low = 0,high = lines.size()-1;
while(low!=high){
int mid = (low+high)/2;
if(intersection(lines[mid],lines[mid+1])<pos){
low = mid+1;
}
else{
high = mid;
}
}
return lines[low].first*pos+lines[low].second;
}
int32_t main() {
ios::sync_with_stdio(0);
cin.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);
}
dp[0] = 0;
update(2*vect1[0],-(vect1[0]*vect1[0]-vect2[0]));
for(int i=1;i<no_of_input;i++){
//cout << query(vect1[i]) << " ";
dp[i] = -query(vect1[i])-vect2[i]+vect1[i]*vect1[i];
update(2*vect1[i],-(dp[i]+vect1[i]*vect1[i]));
}
/*cout << endl;
for(int i=0;i<no_of_input;i++){
cout << dp[i] << ' ';
}
cout << endl;*/
cout << dp[no_of_input-1]+s;
}
Compilation message
building.cpp: In function 'long long int query(long long int)':
building.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<lines.size();i++){
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3083 ms |
3824 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
