This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2603 #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../algorithm/monotoneminima.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int s,n,m; cin>>s>>n>>m; vector<int> xs(s); for(int i=0;i<s;i++) cin>>xs[i]; vector<int> ts(n),ps(n); for(int i=0;i<n;i++) cin>>ts[i]>>ps[i],ps[i]--; vector<int> vs(n); for(int i=0;i<n;i++) vs[i]=ts[i]-xs[ps[i]]; sort(vs.begin(),vs.end()); vector<int> sm(n+1,0); for(int i=0;i<n;i++) sm[i+1]=sm[i]+vs[i]; const int INF = 1e9; vector<int> dp(n+1,INF); dp[0]=0; for(int k=0;k<m;k++){ auto dist= [&](int i,int j){ return i<j?INF:dp[j]+(i?vs[i-1]:0)*(i-j)-(sm[i]-sm[j]); }; auto res=MonotoneMinima::args<int>(n+1,n+1,dist); vector<int> nx(n+1); for(int i=0;i<=n;i++) nx[i]=dist(i,res[i]); swap(dp,nx); } cout<<dp[n]<<endl; return 0; }
#line 1 "test/aoj/2603.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2603 #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "algorithm/monotoneminima.cpp" #line 3 "algorithm/monotoneminima.cpp" using namespace std; #endif //BEGIN CUT HERE namespace MonotoneMinima{ template<typename T,typename F> void induce(int l,int r,int a,int b,vector<int> &dp,F dist){ if(l==r) return; int m=(l+r)>>1; int &idx=(dp[m]=a); T res=dist(m,idx); for(int i=a;i<b;i++){ T tmp=dist(m,i); if(tmp<res) res=tmp,idx=i; } induce<T>(l,m,a,idx+1,dp,dist); induce<T>(m+1,r,idx,b,dp,dist); } // p < q -> argmin f(p, *) <= argmin f(q, *) template<typename T,typename F> vector<int> args(int n,int m,F dist){ vector<int> dp(n,-1); induce<T>(0,n,0,m,dp,dist); return dp; } } //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 8 "test/aoj/2603.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int s,n,m; cin>>s>>n>>m; vector<int> xs(s); for(int i=0;i<s;i++) cin>>xs[i]; vector<int> ts(n),ps(n); for(int i=0;i<n;i++) cin>>ts[i]>>ps[i],ps[i]--; vector<int> vs(n); for(int i=0;i<n;i++) vs[i]=ts[i]-xs[ps[i]]; sort(vs.begin(),vs.end()); vector<int> sm(n+1,0); for(int i=0;i<n;i++) sm[i+1]=sm[i]+vs[i]; const int INF = 1e9; vector<int> dp(n+1,INF); dp[0]=0; for(int k=0;k<m;k++){ auto dist= [&](int i,int j){ return i<j?INF:dp[j]+(i?vs[i-1]:0)*(i-j)-(sm[i]-sm[j]); }; auto res=MonotoneMinima::args<int>(n+1,n+1,dist); vector<int> nx(n+1); for(int i=0;i<=n;i++) nx[i]=dist(i,res[i]); swap(dp,nx); } cout<<dp[n]<<endl; return 0; }