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>
#define all(v) v.begin(), v.end()
#define endl "\n"
#define sz(v) (int)(v).size()
#define int long long
using namespace std;
typedef long long ll;
const int N = 1e6 + 15;
const ll INF = 1e18;
int n;
int h[N];
ll pref[N];
ll dp[N];
struct line{
ll slope, c;
line(ll slope, ll c) : slope(slope), c(c) {}
ll f(ll x) {return slope*x + c;}
};
struct CHT{
vector<line> lines;
bool dump(line d1, line d2, line d3){
return 1.0l*(d1.c - d2.c) / (1.0l*(d2.slope - d1.slope)) <= 1.0l*(d2.c - d3.c) / (1.0l*(d3.slope - d2.slope));
}
void add(line d){
while(sz(lines) > 1 && dump(d, lines.back(), lines[sz(lines)-2])) lines.pop_back();
lines.push_back(d);
}
ll query(ll x){
int l = 0, r = sz(lines)-1;
while(l < r){
int mid = (l+r) >> 1;
if(lines[mid].f(x) >= lines[mid+1].f(x)) l = mid+1;
else r = mid;
}
return lines[l].f(x);
}
void reload(){
while(!lines.empty()) lines.pop_back();
}
} solver;
vector<int> upd;
void dnc(int l, int r){
if(l == r) return;
int mid = (l+r) >> 1;
dnc(l,mid);
for(int i = l; i <= mid; i++) upd.push_back(i);
sort(upd.begin(), upd.end(), [&](int x, int y){
return h[x] < h[y];
});
for(int i : upd) solver.add(line(-2LL*h[i], 1LL*h[i]*h[i] + dp[i] - pref[i]));
for(int i = mid+1; i <= r; i++){
dp[i] = min(dp[i], 1LL*h[i]*h[i] + pref[i-1] + solver.query(h[i]));
}
solver.reload();
while(!upd.empty()) upd.pop_back();
dnc(mid+1,r);
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = 1; i <= n; i++) cin >> pref[i], pref[i] += pref[i-1];
memset(dp, 0x3f, sizeof(dp));
dp[1] = 0;
dnc(1,n);
cout << dp[n];
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(0); cout.tie(0);
#define task "task"
if(fopen(task".INP", "r")){
freopen(task".INP", "r", stdin);
freopen(task".OUT", "w", stdout);
}
int t; t = 1; //cin >> t;
while(t--) solve();
}
Compilation message (stderr)
building.cpp: In function 'int main()':
building.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | freopen(task".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | freopen(task".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |