fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define dbg(var) cout<<#var<<"="<<var<<" "
  4. #define nl cout<<"\n"
  5. #define fr(i,n) for(int i=0;i<n;i++)
  6. #define rep(i,a,n) for(int i=a;i<=n;i++)
  7. #define vi vector<int>
  8. #define vvi vector<vi>
  9. #define pb push_back
  10. #define fa(v) for(auto &i:v)
  11. #define all(v) v.begin(),v.end()
  12. #define sz(v) (int)(v.size())
  13. #define int long long
  14. inline void smax(int &a, int b){a = max(a,b);}
  15. int ternary_search(int l,int r, vector<int> &dp, int a, int b, int wt){
  16.   int ans = 0;
  17.   auto cal = [&](int mid){
  18.   	if(wt-mid*a < 0) return 0LL;
  19.   	return dp[wt-mid*a]+mid*b;
  20.   };
  21.   while(r - l > 5){
  22.   	int mid = l + (r-l)/2;
  23.   	if(cal(mid) > cal(mid+1)) r = mid;
  24.   	else l = mid;
  25.   }
  26.   // rep(i,l,r) cout << cal(i) << " " ;nl;
  27.   rep(i,l,r) smax(ans, cal(i));
  28.   return ans;
  29. }
  30. void solve(){
  31. 	int n,x; cin >> n >> x;
  32. 	vi aa(n),bb(n),cc(n);
  33. 	fr(i,n) cin >> aa[i];
  34. 	fr(i,n) cin >> bb[i];
  35. 	fr(i,n) cin >> cc[i];
  36. 	vi dp(2*x+5);
  37. 	fr(i,n){
  38. 		int a = aa[i], b = bb[i] , c = cc[i];
  39. 		vi tempdp = dp;
  40. 		for(int wt=0;wt<=x+5;wt++){
  41. 			// for(int j=1; j<=c; j++){
  42. 			// 	if(wt - j * a < 0) break;
  43. 			// 	smax(tempdp[wt],dp[wt-j*a]+j*b);
  44. 			// }
  45. 			int l = 1, r = min(wt/a + 1,c);
  46. 			if(l > r) continue;
  47. 			int mx = ternary_search(l,r,dp,a,b,wt);
  48. 			smax(tempdp[wt], mx);
  49. 		}
  50. 		swap(dp,tempdp);
  51. 		// fr(i,x+1) cout << dp[i] << " ";nl;
  52. 	}
  53. 	cout << dp[x];
  54. }
  55. int32_t main()
  56. {
  57.    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  58.    int tst=1; while(tst--){
  59.      solve();
  60.    }
  61. }
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
10 10
1 8 7 3 2 10 3 5 4 7
10 10 6 2 5 1 8 7 5 10
10 1 7 2 9 6 1 5 1 7
stdout
copy 
100
https://ideone.com/Tuo4J8
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!