fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int grid[1005][100005];
  5. int h[1005], s[1005];
  6. int n,x;
  7. bool finished[1005][100005];
  8.  
  9. int solve(int i, int j) {
  10. 	if(i==0) {
  11. 		return 0;
  12. 	}
  13.  
  14. 	if(finished[i][j]) return grid[i][j];
  15. 	finished[i][j]=true;
  16.  
  17. 	// ga diambil
  18. 	grid[i][j]=solve(i-1, j);
  19.  
  20. 	// ambil
  21. 	if(j>=h[i]) {
  22. 		grid[i][j]=max(grid[i][j], solve(i-1, j-h[i])+s[i]);
  23. 	}
  24.  
  25. 	return grid[i][j];
  26. }
  27.  
  28. int main() {
  29. 	cin >> n >> x;
  30.  
  31. 	for(int i=1; i<=n; i++) {
  32. 		cin >> h[i];
  33. 	}
  34. 	for(int i=1; i<=n; i++) {
  35. 		cin >> s[i];
  36. 	}
  37.  
  38. 	for (int i = 1; i <= n; i++) {
  39. 		for (int j = 1; j <= x; j++) {
  40. 			//ga ambil
  41. 			grid[i][j]=grid[i-1][j];
  42.  
  43. 			// ambil
  44. 			if(j>=h[i]) {
  45. 				grid[i][j]=max(grid[i][j], grid[i-1][j-h[i]]+s[i]);
  46. 			}
  47. 		}
  48. 	}
  49. 	cout << grid[n][x] << endl;
  50. }
Success #stdin #stdout 0.01s 7652KB
comments (?)
stdin
copy 
4 10
4 8 5 3
5 12 8 1
stdout
copy 
13
https://ideone.com/KSixcq
language:
C++ (gcc 8.3)
created:
16 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!