#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 110000
#define hmax 1000000
int n, h[maxn], w[maxn], ps[maxn];
int bg[maxn], ed[maxn], a[maxn], b[maxn];
set<pair<int,int>> hull;
int f(int id, int x) {
return a[id]*x + b[id];
}
void ins(int id) {
//f(id) = a[id]*x + b[id];
//onde comeca o id
int lb = 0;
int rb = hmax;
int ansb = -1;
while(lb <= rb) {
int mid = (lb+rb)/2;
//quer saber se f(id) e o melhor no ponto mid
auto it1 = hull.lower_bound(mp(mid,-inf));
int id1 = it1->sc;
if(f(id,mid) <= f(id1,mid)) {
//id e otimo em mid, o comeco esta em (lb,mid)
ansb = mid;
rb = mid-1;
}
else {
//id nao e otimo em mid, comeco esta em (mid+1,rb)
if(a[id] < a[id1]) {
//comeco esta em (mid+1,rb)
lb = mid+1;
}
else {
rb = mid-1;
}
}
}
//nao e bom em nenhum ponto
if(ansb == -1) return;
//onde comeca o id
int le = 0;
int re = hmax;
int anse = -1;
while(le <= re) {
int mid = (le+re)/2;
//quer saber se f(id) e o melhor no ponto mid
auto it1 = hull.lower_bound(mp(mid,-inf));
int id1 = it1->sc;
if(f(id,mid) <= f(id1,mid)) {
//id e otimo em mid, o final esta em (mid,rb)
anse = mid;
le = mid+1;
}
else {
//id e otimo em mid, o final esta em (lb,mid-1)
re = mid-1;
if(a[id] < a[id1]) {
//final esta em (mid+1,rb)
le = mid+1;
}
else {
re = mid-1;
}
}
}
//id e otimo em (ansb, anse)
auto itb = hull.lower_bound(mp(ansb,-inf));
int idb = itb->sc;
auto ite = hull.lower_bound(mp(anse,-inf));
int ide = ite->sc;
ite++;
hull.erase(itb,ite);
//se for interir idb
if(bg[idb] < ansb) {
ed[idb] = ansb-1;
hull.insert(mp(ed[idb],idb));
}
//se for interir ide
if(ed[ide] > anse) {
bg[ide] = anse+1;
hull.insert(mp(ed[ide],ide));
}
//insere id
bg[id] = ansb;
ed[id] = anse;
hull.insert(mp(ed[id],id));
}
void solve() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> h[i];
}
for(int i = 1; i <= n; i++) {
cin >> w[i];
ps[i] = ps[i-1] + w[i];
}
bg[0] = 0;
ed[0] = hmax;
a[0] = 0;
b[0] = inf;
hull.insert(mp(hmax,0));
a[n] = -2*h[n];
b[n] = h[n]*h[n] + ps[n-1];
ins(n);
for(int i = n-1; i >= 2; i--) {
auto it1 = hull.lower_bound(mp(h[i],-inf));
int id1 = it1->sc;
int ans1 = f(id1,h[i]) + h[i]*h[i] - ps[i];
a[i] = -2*h[i];
b[i] = ans1 + h[i]*h[i] + ps[i-1];
ins(i);
}
auto it = hull.lower_bound(mp(h[1],-inf));
int id = it->sc;
int ans = f(id,h[1]) + h[1]*h[1] - ps[1];
cout << ans << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
324 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
436 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
5696 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
324 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
436 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
