#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = 1e5 + 10;
const int BUCKET = 320;
const ll INF = 1e18;
struct line{
ll a,b;
line(ll _a = 0,ll _b = 0){
a = _a;
b = _b;
}
ll get(ll x){return a*x + b;}
ld get_ld(ld x){return a*x + b;}
bool operator<(const line& other)const{
if(a != other.a) return a > other.a;
return b > other.b;
}
};
vector<line> hull,light_lines;
ll dp[MAXN],H[MAXN],W[MAXN],pref[MAXN],b[MAXN],a[MAXN];
int N;
ld inter(line l1,line l2){
return -1.0*ld(l1.b - l2.b)/ld(l1.a - l2.a);
}
bool useless(line l1,line l2,line l3){
ld x = inter(l1,l3);
return l2.get_ld(x) > l3.get_ld(x);
}
void add_line(line l){
while(!hull.empty() && hull.back().a == l.a){
hull.pop_back();
}
while(!hull.empty() && useless(hull[hull.size()-2],hull.back(),l)){
hull.pop_back();
}
hull.push_back(l);
}
void rebuild(){
vector<line> temp;
sort(light_lines.begin(),light_lines.end());
merge(hull.begin(),hull.end(),light_lines.begin(),light_lines.end(),back_inserter(temp));
hull.clear();
light_lines.clear();
for(line l : temp){
add_line(l);
}
}
void add(ll a,ll b){
line l(a,b);
light_lines.push_back(l);
if(light_lines.size() >= BUCKET) rebuild();
}
ll query(ll x){
ll ans = INF;
for(line l : light_lines) ans = min(ans, l.get(x) );
if(hull.empty()) return ans;
ans = min(ans, hull.back().get(x) );
int ini = 0,fim = hull.size() - 2,meio;
while(ini <= fim){
meio = ini + (fim - ini)/2;
ll f1 = hull[meio].get(x),f2 = hull[meio+1].get(x);
ans = min(ans, min(f1,f2) );
if(f1 < f2){
fim = meio - 1;
}
else{
ini = meio + 1;
}
}
return min(ans,hull[meio].get(x));
}
int main(){
scanf("%d",&N);
for(int i = 1;i<=N;i++){
scanf("%lld",&H[i]);
}
for(int i = 1;i<=N;i++){
scanf("%lld",&W[i]);
pref[i] = W[i] + pref[i-1];
}
dp[1] = 0;
a[1] = -2*H[1];
b[1] = -pref[1] + dp[1] + H[1]*H[1];
add(a[1],b[1]);
for(int i = 2;i<=N;i++){
dp[i] = query(H[i]) + H[i]*H[i] + pref[i-1];
a[i] = -2*H[i];
b[i] = -pref[i] + dp[i] + H[i]*H[i];
add(a[i],b[i]);
}
cout << dp[N] << endl;
return 0;
}
Compilation message
building.cpp: In function 'int main()':
building.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
~~~~~^~~~~~~~~
building.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&H[i]);
~~~~~^~~~~~~~~~~~~~
building.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&W[i]);
~~~~~^~~~~~~~~~~~~~
building.cpp: In function 'll query(ll)':
building.cpp:78:36: warning: 'meio' may be used uninitialized in this function [-Wmaybe-uninitialized]
int ini = 0,fim = hull.size() - 2,meio;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
520 KB |
Output is correct |
| 4 |
Correct |
3 ms |
520 KB |
Output is correct |
| 5 |
Correct |
3 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
5348 KB |
Output is correct |
| 2 |
Correct |
90 ms |
5432 KB |
Output is correct |
| 3 |
Correct |
91 ms |
5432 KB |
Output is correct |
| 4 |
Correct |
112 ms |
5432 KB |
Output is correct |
| 5 |
Incorrect |
105 ms |
5440 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
520 KB |
Output is correct |
| 4 |
Correct |
3 ms |
520 KB |
Output is correct |
| 5 |
Correct |
3 ms |
600 KB |
Output is correct |
| 6 |
Correct |
96 ms |
5348 KB |
Output is correct |
| 7 |
Correct |
90 ms |
5432 KB |
Output is correct |
| 8 |
Correct |
91 ms |
5432 KB |
Output is correct |
| 9 |
Correct |
112 ms |
5432 KB |
Output is correct |
| 10 |
Incorrect |
105 ms |
5440 KB |
Output isn't correct |
