fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned long long
  4. #define FNAME "THIEF"
  5. #define xd "\n"
  6. using namespace std;
  7. const int MAXN = (int)1e6 + 1;
  8. const long long INF = (long long)1e12;
  9. const long long MOD = (long long)1e9 + 7;
  10.  
  11. template<class X, class Y>
  12. 	bool minimize(X &a , Y b){
  13. 		if(a > b){
  14. 			a = b;
  15. 			return true;
  16. 		}
  17. 		return false;
  18. 	}
  19.  
  20. template<class X, class Y>
  21. 	bool maximize(X &a , Y b){
  22. 		if(a < b){
  23. 			a = b;
  24. 			return true;
  25. 		}
  26. 		return false;
  27. 	}
  28.  
  29. void HuuThien(){
  30. 	ios_base::sync_with_stdio(0);
  31. 	cin.tie(0); cout.tie(0);
  32. 	if(fopen(FNAME".inp","r")){
  33. 		freopen(FNAME".inp","r",stdin);
  34. 		freopen(FNAME".out","w",stdout);
  35. 	}
  36. }
  37.  
  38. int n;
  39. int Maxv = 0;
  40. long long W, K;
  41. vector<long long> w;
  42. vector<int> v;
  43.  
  44. void Init() {
  45. 	cin >> n >> W >> K;
  46. 	w.assign(n + 1, 0);
  47. 	v.assign(n + 1, 0);
  48.  
  49. 	for(int i = 1; i <= n ; i++) {
  50. 		cin >> w[i];
  51. 	}
  52.  
  53. 	for(int i = 1; i <= n ; i++) {
  54. 		cin >> v[i];
  55. 		Maxv += v[i];
  56. 	}
  57. } 
  58.  
  59. void Solve() {
  60. 	long long res = 0;
  61.  
  62. 	for(int take = 1; take <= n ; take++) {
  63. 		if(w[take] > K) continue;
  64. 		vector<long long> dp(Maxv + 1, INF);
  65. 		dp[0] = 0;
  66. 		for(int i = 1; i <= n ; i++) {
  67. 			if(i == take) continue;
  68. 			for(int j = Maxv; j >= v[i]; j--) {
  69. 				if(dp[j - v[i]] + w[i] <= W) {
  70. 					dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
  71. 				}
  72. 			}
  73. 		}
  74.  
  75. 		long long ans = 0;
  76. 		for(int i = Maxv; i >= 1 ; i--) {
  77. 			if(dp[i] <= W) {
  78. 				ans = i;
  79. 				break;
  80. 			}
  81. 		}
  82. 		maximize(res, ans + v[take]);
  83. 	}
  84.  
  85. 	cout << res;
  86. } 
  87.  
  88. signed main(){
  89. 	HuuThien();	
  90. 	int test = 1;
  91. 	while(test--){
  92. 		Init();
  93. 		Solve();
  94. 	}
  95. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2gZK4B
language:
C++ (gcc 8.3)
created:
5 days 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!