This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0613" #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../tools/fixpoint.cpp" #include "../../tools/chminmax.cpp" #include "../../vector/compress.cpp" #include "../../datastructure/rangeslide.cpp" #undef call_from_test #ifdef SANITIZE #define IGNORE #endif signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n; ll d; cin>>n>>d; vector<ll> xs(n),ys(n); for(int i=0;i<n;i++) cin>>xs[i]>>ys[i]; if(n==1){ cout<<(xs[0]<=d?ys[0]:0)<<endl; return 0; } int h=n/2; using P = pair<ll, ll>; auto calc= [&](int a,int b){ vector<P> res; MFP([&](auto dfs,int k,ll s,ll t)->void{ if(k==b){ res.emplace_back(s,t); return; } dfs(k+1,s,t); dfs(k+1,s+xs[k],t+ys[k]); dfs(k+1,s-xs[k],t-ys[k]); })(a,0,0); sort(res.begin(),res.end()); return res; }; auto v1=calc(0,h); auto v2=calc(h,n); reverse(v2.begin(),v2.end()); const ll INF = 1e17; vector<ll> vs; for(auto p:v1) vs.emplace_back(p.first); vs.emplace_back(-INF); vs.emplace_back(+INF); vs=compress(vs); vector<ll> ws(vs.size(),-INF); { int k=0; for(auto p:v1){ while(vs[k]<p.first) k++; chmax(ws[k],p.second); } } v1.clear(); auto cmp=[](ll a,ll b){return a>b;}; RangeSlide<ll, decltype(cmp)> slide(ws,cmp); vector<ll> ks; { int l=0,r=0; for(auto p:v2){ ll x=p.first,k=p.second; while(l<(int)vs.size()&&vs[l]< -x-d) l++; while(r<(int)vs.size()&&vs[r]<=-x+d) r++; if(l==r) continue; slide.add_range(l,r); ks.emplace_back(k); } } vs.clear(); v2.clear(); auto res=slide.build(); ll ans=0; for(int i=0;i<(int)res.size();i++) chmax(ans,ws[res[i]]+ks[i]); cout<<ans<<endl; return 0; }
#line 1 "test/aoj/0613.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0613" #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "tools/fixpoint.cpp" #line 3 "tools/fixpoint.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename F> struct FixPoint : F{ FixPoint(F&& f):F(forward<F>(f)){} template<typename... Args> decltype(auto) operator()(Args&&... args) const{ return F::operator()(*this,forward<Args>(args)...); } }; template<typename F> inline decltype(auto) MFP(F&& f){ return FixPoint<F>{forward<F>(f)}; } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 1 "tools/chminmax.cpp" #line 3 "tools/chminmax.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 1 "vector/compress.cpp" #line 3 "vector/compress.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename V> V compress(V vs){ sort(vs.begin(),vs.end()); vs.erase(unique(vs.begin(),vs.end()),vs.end()); return vs; } template<typename T> map<T, int> dict(const vector<T> &vs){ map<T, int> res; for(int i=0;i<(int)vs.size();i++) res[vs[i]]=i; return res; } map<char, int> dict(const string &s){ return dict(vector<char>(s.begin(),s.end())); } template<typename T> vector<T> compressed(vector<T> vs){ auto dc=dict(compress(vs)); for(auto &v:vs) v=dc[v]; return vs; } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 1 "datastructure/rangeslide.cpp" #line 3 "datastructure/rangeslide.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T, typename F> struct RangeSlide{ vector<size_t> ls,rs; vector<T> vs; F cmp; RangeSlide(vector<T> vs,F cmp):vs(vs),cmp(cmp){} void add_range(size_t l,size_t r){ ls.emplace_back(l); rs.emplace_back(r); } vector<size_t> build(){ deque<size_t> deq; vector<size_t> res; for(size_t i=0,l=0,r=0;i<ls.size();i++){ if(r<=ls[i]){ deq.clear(); l=r=ls[i]; } while(r<rs[i]){ while(!deq.empty() and !cmp(vs[deq.back()],vs[r])) deq.pop_back(); deq.emplace_back(r++); } while(l<ls[i]){ if(deq.front()==l++) deq.pop_front(); } res.emplace_back(deq.front()); } return res; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 11 "test/aoj/0613.test.cpp" #undef call_from_test #ifdef SANITIZE #define IGNORE #endif signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n; ll d; cin>>n>>d; vector<ll> xs(n),ys(n); for(int i=0;i<n;i++) cin>>xs[i]>>ys[i]; if(n==1){ cout<<(xs[0]<=d?ys[0]:0)<<endl; return 0; } int h=n/2; using P = pair<ll, ll>; auto calc= [&](int a,int b){ vector<P> res; MFP([&](auto dfs,int k,ll s,ll t)->void{ if(k==b){ res.emplace_back(s,t); return; } dfs(k+1,s,t); dfs(k+1,s+xs[k],t+ys[k]); dfs(k+1,s-xs[k],t-ys[k]); })(a,0,0); sort(res.begin(),res.end()); return res; }; auto v1=calc(0,h); auto v2=calc(h,n); reverse(v2.begin(),v2.end()); const ll INF = 1e17; vector<ll> vs; for(auto p:v1) vs.emplace_back(p.first); vs.emplace_back(-INF); vs.emplace_back(+INF); vs=compress(vs); vector<ll> ws(vs.size(),-INF); { int k=0; for(auto p:v1){ while(vs[k]<p.first) k++; chmax(ws[k],p.second); } } v1.clear(); auto cmp=[](ll a,ll b){return a>b;}; RangeSlide<ll, decltype(cmp)> slide(ws,cmp); vector<ll> ks; { int l=0,r=0; for(auto p:v2){ ll x=p.first,k=p.second; while(l<(int)vs.size()&&vs[l]< -x-d) l++; while(r<(int)vs.size()&&vs[r]<=-x+d) r++; if(l==r) continue; slide.add_range(l,r); ks.emplace_back(k); } } vs.clear(); v2.clear(); auto res=slide.build(); ll ans=0; for(int i=0;i<(int)res.size();i++) chmax(ans,ws[res[i]]+ks[i]); cout<<ans<<endl; return 0; }