fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6. 	int n;
  7. 	scanf("%d", &n);
  8. 	int c[n];
  9. 	for (int i = 0; i < n; i++) {
  10. 		scanf("%d", &c[i]);
  11. 	}
  12. 	int k;
  13. 	scanf("%d", &k);
  14. 	int dp[k+1];
  15. 	dp[0] = 0;
  16. 	for (int i = 1; i <= k; i++) {
  17. 		dp[i] = 1e9;
  18. 		for (int j = 0; j < n; j++) {
  19. 			if (i >= c[j]) {
  20. 				dp[i] = min(dp[i], dp[i-c[j]]+1);
  21. 			}
  22. 		}
  23. 	}
  24. 	if (dp[k] == 1e9) {
  25. 		printf("-1");
  26. 	} else {
  27. 		printf("%d", dp[k]);
  28. 	}
  29. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
4
1 2 5 6
10
stdout 
2
https://ideone.com/xtpXhw
language:
C++ (gcc 8.3)
created:
15 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!