#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Bridges"
int n, m;
int h[100001];
int x[100001];
int w[100001];
class line{
public:
ll a, b;
line(){
a=0;
b=1e18;
}
line(ll a, ll b){
this->a=a;
this->b=b;
}
ll at(int x){
return a*x+b;
}
};
class linear_segment_tree{
public:
using pointer=linear_segment_tree*;
pointer left, right;
int l, r, m;
line L;
linear_segment_tree(int idl, int idr): L(){
l=x[idl];
r=x[idr];
m=x[(idl+idr)/2];
if(idl!=idr){
left=new linear_segment_tree(idl, (idl+idr)/2);
right=new linear_segment_tree((idl+idr)/2+1, idr);
}
}
void update(line A){
bool gl=A.at(l)<=L.at(l);
bool gr=A.at(r)<=L.at(r);
if(gl&&gr) L=A;
else if(gl||gr){
left->update(A);
right->update(A);
}
}
ll get(int u){
if(l==r) return L.at(u);
else{
if(m>=u) return min(left->get(u), L.at(u));
return min(right->get(u), L.at(u));
}
}
};
linear_segment_tree::pointer tree;
int main(){
#ifdef Aria
if(fopen(taskname".in", "r"))
freopen(taskname".in", "r", stdin);
#endif // Aria
read(n);
FOR(i, 1, n) read(h[i]);
FOR(i, 1, n) read(w[i]);
FOR(i, 1, n) x[i]=h[i];
sort(x+1, x+n+1);
m=unique(x+1, x+n+1)-x-1;
tree=new linear_segment_tree(1, m);
tree->update(line(-h[1]*2, ((ll)h[1])*h[1]));
ll ans=0;
FOR(i, 2, n){
ll best=tree->get(h[i]);
best+=((ll)h[i])*h[i]-w[i];
tree->update(line(-h[i]*2, best+((ll)h[i])*h[i]));
if(i==n) ans=best;
}
ans+=accumulate(w+1, w+n+1, 0LL);
writeln(ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
