This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM https://yukicoder.me/problems/2113 #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../io/single.cpp" #include "../../algorithm/offlineonline.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n; cin>>n; auto as=read<ll>(n); auto xs=read<ll>(n); auto ys=read<ll>(n); auto dist= [&](int i,int j)->ll{ ll s=abs(xs[i]-as[j-1]); ll t=abs(ys[i]); return s*s*s+t*t*t; }; cout<<OfflineOnline::solve<ll>(n,dist)<<endl; return 0; }
#line 1 "test/yukicoder/2113.test.cpp" // verification-helper: PROBLEM https://yukicoder.me/problems/2113 #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "io/single.cpp" #line 3 "io/single.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T=int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 1 "algorithm/offlineonline.cpp" #line 3 "algorithm/offlineonline.cpp" using namespace std; #endif // https://qiita.com/tmaehara/items/0687af2cfb807cde7860 //BEGIN CUT HERE namespace OfflineOnline{ vector<int> used; template<typename T> void update(vector<T> &dp,int k,T val){ if(!used[k]) dp[k]=val; dp[k]=min(dp[k],val); used[k]=1; } // [l, r), [a, b] template<typename T,typename F> void induce(int l,int r,int a,int b,vector<T> &dp,F dist){ if(l==r) return; int m=(l+r)>>1; assert(m<a); int idx=a; T res=dist(m,idx)+dp[idx]; for(int i=a;i<=b;i++){ T tmp=dist(m,i)+dp[i]; if(tmp<res) res=tmp,idx=i; } update(dp,m,res); induce(l,m+0,a,idx,dp,dist); induce(m+1,r,idx,b,dp,dist); } template<typename T,typename F> void solve(int l,int r,vector<T> &dp,F dist){ if(l+1==r) return update(dp,l,dist(l,r)+dp[r]); int m=(l+r)>>1; solve(m,r,dp,dist); induce(l,m,m,r,dp,dist); solve(l,m,dp,dist); } // dp[i] = min_{i<j} dist(i,j) + dp[j] template<typename T,typename F> T solve(int n,F dist){ vector<T> dp(n+1,0); used.assign(n+1,0); used[n]=1; solve(0,n,dp,dist); return dp[0]; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 9 "test/yukicoder/2113.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n; cin>>n; auto as=read<ll>(n); auto xs=read<ll>(n); auto ys=read<ll>(n); auto dist= [&](int i,int j)->ll{ ll s=abs(xs[i]-as[j-1]); ll t=abs(ys[i]); return s*s*s+t*t*t; }; cout<<OfflineOnline::solve<ll>(n,dist)<<endl; return 0; }