#include<bits/stdc++.h>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define div ___div
#define next ___next
#define prev ___prev
#define left ___left
#define right ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X,class Y>
void minimize(X &x,const Y &y) {
if (x>y) x=y;
}
template<class X,class Y>
void maximize(X &x,const Y &y) {
if (x<y) x=y;
}
template<class T>
T Abs(const T &x) {
return (x<0?-x:x);
}
/* Author: Phat Truong */
const int maxn = 1e5 + 10;
bool line_sort(false);
struct line{
long long m,b;
mutable double p;
line();
line(long long _m,long long _b,double _p){
m = _m,b = _b,p = _p;
}
bool operator < (const line &x) const{
if(!line_sort){
if(m == x.m) return b < x.b;
return m > x.m;
}
return p < x.p;
}
};
struct line_container:multiset<line,less<>>{
const double inf = 1/.0;
bool intersect(iterator x,iterator y){
if(y == end()){
x->p = inf;
return false;
}
if(x -> m == y ->m)
return true;
else
x->p = (x ->b - y->b)*1.0/(y -> m - x ->m);
return x ->p >= y->p;
}
void add(long long m,long long b){
iterator z = insert(line(m,b,0));
iterator y = z++;
iterator x = y;
while(intersect(y,z))
intersect(y, z = erase(z));
while((x = y) != begin() && intersect(--x,y))
intersect(x,y = erase(y));
while((y = x) != begin() && intersect(--x,y))
intersect(x,y = erase(y));
}
long long findval(long long x){
line_sort = true;
line t = *(lower_bound(line(0,0,x)));
line_sort = false;
return (x*t.m + t.b);
}
};
line_container hull;
long long dp[maxn];
int n;
long long h[maxn];
long long w[maxn];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
// freopen("test.inp","r",stdin);
// freopen("test.out","w",stdout);
cin >> n;
FOR(i,1,n)
cin >> h[i];
FOR(i,1,n)
cin >> w[i];
FOR(i,1,n)
w[i] += w[i-1];
hull.add(-2*h[1],h[1]*h[1]);
dp[1] = 0;
FOR(i,2,n){
long long tmp = hull.findval(h[i]);
dp[i] = tmp + h[i]*h[i] + w[i - 1];
hull.add(-2*h[i],h[i]*h[i] - w[i] + dp[i]);
}
cout << dp[n];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
2760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
