fork download
copy 
  1. /* Man Mohan Mishra
  2.    IIIT Allahabad
  3. */
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. int c[10];
  9. int p[1005];
  10. int v[1005];
  11. long long dp[1005][33];
  12. long long temp[1005][33];
  13.  
  14. int main()
  15. {
  16. 	//freopen("inp_12.txt","r",stdin);
  17. 	//freopen("out_12.txt","w",stdout);
  18. 	int t;
  19. 	scanf("%d",&t);
  20. 	if (t < 1 || t > 3) {
  21. 		printf("error\n");
  22. 		return 0;
  23. 	}
  24. 	while (t --) {
  25. 		int n,m,k,i,j,x,y;
  26. 		long long ans;
  27. 		scanf("%d%d%d",&n,&m,&k);
  28. 		if (n < 1 || n > 1000) {
  29. 			printf("error\n");
  30. 			return 0;
  31. 		}
  32. 		if (m < 1 || m > 1000) {
  33. 			printf("error\n");
  34. 			return 0;
  35. 		}
  36. 		if (k < 1 || k > 5) {
  37. 			printf("error\n");
  38. 			return 0;
  39. 		}
  40. 		for (i = 0; i < k; i++) {
  41. 			scanf("%d",&c[i]);
  42. 			if (c[i] < 1 || c[i] > 1000000000) {
  43. 				printf("error\n");
  44. 				return 0;
  45. 			}
  46. 		}
  47. 		for (i = 0; i < n; i++) {
  48. 			scanf("%d",&p[i]);
  49. 			if (p[i] < 1 || p[i] > 1000000000) {
  50. 				printf("error\n");
  51. 				return 0;
  52. 			}
  53. 		}
  54. 		for (i = 0; i < n; i++) {
  55. 			scanf("%d",&v[i]);
  56. 			if (v[i] < 1 || v[i] > 1000000000) {
  57. 				printf("error\n");
  58. 				return 0;
  59. 			}
  60. 		}
  61. 		memset(dp,-1,sizeof(dp));
  62. 		dp[0][0] = 0;
  63. 		for (i = 0; i < n; i++) {
  64. 			for (j = 0; j <= m; j++) {
  65. 				for (x = 0; x < (1 << k); x++) {
  66. 					temp[j][x] = dp[j][x];
  67. 				}
  68. 			}
  69. 			for (j = 0; j <= m; j++) {
  70. 				for (x = 0; x < (1 << k); x++) {
  71. 					if (dp[j][x] == -1) continue;
  72. 					for (y = 0; y < k; y++) {
  73. 						if (((x >> y) & 1) == 0 && c[y] >= v[i]) {
  74. 							if (j + p[i] <= m) {
  75. 								temp[j + p[i]][(x + (1 << y))] = max(temp[j + p[i]][(x + (1 << y))],dp[j][x] + v[i]);
  76. 							}
  77. 						}
  78. 					}
  79. 				}
  80. 			}
  81. 			for (j = 0; j <= m; j++) {
  82. 				for (x = 0; x < (1 << k); x++) {
  83. 					dp[j][x] = temp[j][x];
  84. 				}
  85. 			}
  86. 		}
  87. 		ans = 0LL;
  88. 		for (j = 0; j <= m; j++) {
  89. 			for (x = 0; x < (1 << k); x++) {
  90. 				ans = max(ans,dp[j][x]);
  91. 			}
  92. 		}
  93. 		printf("%lld\n",ans);
  94. 	}
  95. 	return 0;
  96. }
Success #stdin #stdout 0s 3984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
error
https://ideone.com/mYMGK5
language:
C++ (gcc 8.3)
created:
7 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!