#include <bits/stdc++.h>
#define DIM 100010
#define DIMM 1000010
#define INF 1000000000000000000LL
using namespace std;
pair <long long,long long> aint[DIMM*4];
long long h[DIM],w[DIM],sp[DIM],dp[DIM];
long long n,i;
long long maxi;
long long f (long long a, long long b, long long x){
return a*x+b;
}
void add (long long nod, long long st, long long dr, long long a, long long b){
if (st == dr){
if (f(a,b,st) < f(aint[nod].first,aint[nod].second,st))
aint[nod] = make_pair (a,b);
return;
}
long long mid = (st+dr)>>1;
int ok_mid = 0, ok_dr = 0;
if (f(a,b,mid) < f(aint[nod].first,aint[nod].second,mid))
ok_mid = 1;
if (f(a,b,dr) < f(aint[nod].first,aint[nod].second,dr))
ok_dr = 1;
if (!ok_mid && !ok_dr) /// ma duc in stanga
add (nod<<1,st,mid,a,b);
else {
if (!ok_mid && ok_dr)
add ((nod<<1)|1,mid+1,dr,a,b);
else {
/// inseamna ca ok_mid = 1
swap (aint[nod].first,a);
swap (aint[nod].second,b);
if (ok_dr)
add (nod<<1,st,mid,a,b);
else add ((nod<<1)|1,mid+1,dr,a,b);
}
}
}
long long query (long long nod, long long st, long long dr, long long x){
if (st == dr)
return f(aint[nod].first,aint[nod].second,x);
long long mid = (st+dr)>>1;
long long sol = INF;
if (x <= mid)
sol = query (nod<<1,st,mid,x);
else sol = query ((nod<<1)|1,mid+1,dr,x);
return min (sol,f(aint[nod].first,aint[nod].second,x));
}
void init (long long nod, long long st, long long dr){
aint[nod] = make_pair(INF,INF);
if (st == dr)
return;
long long mid = (st+dr)>>1;
init (nod<<1,st,mid);
init ((nod<<1)|1,mid+1,dr);
}
int main (){
cin>>n;
for (i=1;i<=n;i++){
cin>>h[i];
maxi = max (maxi,h[i]);
}
for (i=1;i<=n;i++){
cin>>w[i];
sp[i] = sp[i-1] + w[i];
}
/// pe primul si ultimul le iau obligatoriu
/// dp[i] - costul minim sa ajung in i
//for (i=2;i<=n;i++)
// dp[i] = (h[i]-h[1])*(h[i]-h[1]) + sp[i-1]-sp[1];
init (1,0,maxi);
add (1,0,maxi,-2*h[1],h[1]*h[1]-w[1]);
for (i=2;i<=n;i++){
dp[i] = h[i]*h[i] + sp[i-1] + query (1,0,maxi,h[i]);
add (1,0,maxi,-2*h[i],dp[i]+h[i]*h[i]-sp[i]);
}
cout<<dp[n];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
7520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
