// cre: Nguyen Ngoc Hung - Train VOI 2024
#include<bits/stdc++.h>
using namespace std;
#define __nnhzzz__ signed main()
#define BIT(i,j) ((i>>j)&1LL)
#define MASK(i) (1LL<<i)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define gcd __gcd
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i+=c)
#define endl "\n"
#define int ll
//-------------------------------------------------------------//
const int inf = 1e15,LOG = 20,MAXN = 1e6+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T> bool mini(T &a, const T &b){if(a>b){a=b;return true;}return false;}
template<typename T> bool maxi(T &a, const T &b){if(a<b){a=b;return true;}return false;}
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Nguyen Ngoc Hung - nnhzzz
Training for VOI24 gold medal
----------------------------------------------------------------
*/
//pii a[MAXN];
//int pre[MAXN],dp[MAXN];
//int n;
//
//int sqr(int x){
// return 1LL*x*x;
//}
//
//int f(int l, int r){
// if(l>r) return 0LL;
// return pre[r]-pre[l-1];
//}
//int cost(int i, int j){
// return sqr(a[i].fi-a[j].fi);
//}
//void sub1(){
// if(n>2) sort(a+2,a+n,[&](const pii &i, const pii &j){
// return i.se<j.se;
// });
// REP(i,1,n) pre[i] = pre[i-1]+a[i].fi;
// REP(i,2,n){
// dp[i] = f(2,i-1)+cost(1,i);
// REP(j,2,i-1){
// mini(dp[i],dp[j-1]+f(j+1,i-1)+cost(j,i));
// }
// }
// cout << dp[n];
//}
struct Line{
int a,b;
Line(int a = 0, int b = inf):a(a),b(b){}
int f(int x){
return a*x+b;
}
}st[MAXN<<2];
void update(int id, int l, int r, Line x){
if(st[id].f(l)>=x.f(l) && st[id].f(r)>=x.f(r)){
st[id] = x; return ;
}
if(st[id].f(l)<=x.f(l) && st[id].f(r)<=x.f(r)) return ;
int mid = (l+r)>>1;
update(id<<1,l,mid,x);
update(id<<1|1,mid+1,r,x);
}
int get(int id, int l, int r, int x){
if(l==r) return st[id].f(x);
int res = st[id].f(x);
int mid = (l+r)>>1;
if(x<=mid) mini(res,get(id<<1,l,mid,x)); else mini(res,get(id<<1|1,mid+1,r,x));
return res;
}
//(Hi - Hj) * (Hi - Hj) = Hi * Hi - (2 * Hj) * Hi + (Hj * Hj)
int h[MAXN],w[MAXN],dp[MAXN];
int n;
void sub3(){
dp[1] = -w[1];
update(1,0,MAXN-1,Line(-2LL*h[1],1LL*h[1]*h[1]+dp[1]));
REP(i,2,n){
dp[i] = get(1,0,MAXN-1,h[i])+1LL*h[i]*h[i]-w[i];
update(1,0,MAXN-1,Line(-2LL*h[i],1LL*h[i]*h[i]+dp[i]));
}
int res = dp[n];
REP(i,1,n) res += w[i];
cout << res;
}
void solve(){
cin >> n;
REP(i,1,n) cin >> h[i];
REP(i,1,n) cin >> w[i];
sub3(); return ;
if(n<=2000){
// sub1();
return ;
}
}
__nnhzzz__{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "test"
if(fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
#define name1 "nnhzzz"
if(fopen(name1".inp","r")){
freopen(name1".inp","r",stdin);
freopen(name1".out","w",stdout);
}
int test = 1;
while(test--){
solve();
}
cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
return 0;
}
Compilation message
building.cpp: In function 'int main()':
building.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | freopen(name1".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
139 | freopen(name1".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
67764 KB |
Output is correct |
| 2 |
Correct |
10 ms |
67908 KB |
Output is correct |
| 3 |
Correct |
10 ms |
67676 KB |
Output is correct |
| 4 |
Correct |
10 ms |
67928 KB |
Output is correct |
| 5 |
Correct |
10 ms |
67932 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
54 ms |
73204 KB |
Output is correct |
| 2 |
Correct |
54 ms |
73044 KB |
Output is correct |
| 3 |
Correct |
57 ms |
73052 KB |
Output is correct |
| 4 |
Correct |
51 ms |
73108 KB |
Output is correct |
| 5 |
Correct |
46 ms |
72968 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
67764 KB |
Output is correct |
| 2 |
Correct |
10 ms |
67908 KB |
Output is correct |
| 3 |
Correct |
10 ms |
67676 KB |
Output is correct |
| 4 |
Correct |
10 ms |
67928 KB |
Output is correct |
| 5 |
Correct |
10 ms |
67932 KB |
Output is correct |
| 6 |
Correct |
54 ms |
73204 KB |
Output is correct |
| 7 |
Correct |
54 ms |
73044 KB |
Output is correct |
| 8 |
Correct |
57 ms |
73052 KB |
Output is correct |
| 9 |
Correct |
51 ms |
73108 KB |
Output is correct |
| 10 |
Correct |
46 ms |
72968 KB |
Output is correct |
| 11 |
Correct |
54 ms |
73380 KB |
Output is correct |
| 12 |
Correct |
58 ms |
73184 KB |
Output is correct |
| 13 |
Correct |
41 ms |
73276 KB |
Output is correct |
| 14 |
Correct |
55 ms |
73352 KB |
Output is correct |
| 15 |
Correct |
45 ms |
73044 KB |
Output is correct |
| 16 |
Correct |
52 ms |
73052 KB |
Output is correct |
| 17 |
Correct |
33 ms |
73040 KB |
Output is correct |
| 18 |
Correct |
29 ms |
73040 KB |
Output is correct |
