fork download
  1. // 2015-11-04
  2. #include <iostream>
  3. #include <bitset>
  4. #include <vector>
  5. #include <cstdio>
  6. using namespace std;
  7. int main() {
  8. int T;
  9. cin >> T;
  10. for (int _cs = 1; _cs <= T; _cs++) {
  11. int N;
  12. cin >> N;
  13. int sum = 0;
  14. vector<int> x(N);
  15. for (int i = 0; i < N; i++) {
  16. cin >> x[i];
  17. sum += x[i];
  18. }
  19. printf("Case %d: ", _cs);
  20. if (sum%2 || N%2) {
  21. puts("No");
  22. continue;
  23. }
  24. vector<bitset<41>> dp(sum+1);
  25. dp[0][0] = 1;
  26. for (int i = 0; i < N; i++) {
  27. for (int j = dp.size() -1; j >= x[i]; j--) {
  28. dp[j] |= dp[j-x[i]] << 1;
  29. }
  30. }
  31. puts(dp[sum/2][N/2] ? "Yes" : "No");
  32. }
  33. }
  34.  
Success #stdin #stdout 0s 15224KB
stdin
23
stdout
Case 1: Yes
Case 2: Yes
Case 3: Yes
Case 4: Yes
Case 5: Yes
Case 6: Yes
Case 7: Yes
Case 8: Yes
Case 9: Yes
Case 10: Yes
Case 11: Yes
Case 12: Yes
Case 13: Yes
Case 14: Yes
Case 15: Yes
Case 16: Yes
Case 17: Yes
Case 18: Yes
Case 19: Yes
Case 20: Yes
Case 21: Yes
Case 22: Yes
Case 23: Yes