mickypinata

USACO-T027: Subset Sums

Nov 30th, 2021
686
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: subset
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. typedef long long lli;
  11.  
  12. const int N = 39 + 5;
  13. const int X = 39 * 40 / 4 + 5;
  14.  
  15. lli dp[N][X];
  16.  
  17. int main(){
  18.     freopen("subset.in", "r", stdin);
  19.     freopen("subset.out", "w", stdout);
  20.  
  21.     int n;
  22.     scanf("%d", &n);
  23.     int sum = n * (n + 1) / 2;
  24.     if(sum % 2 == 1){
  25.         cout << "0\n";
  26.         fclose(stdin);
  27.         fclose(stdout);
  28.         return 0;
  29.     }
  30.     int tr = sum / 2;
  31.     for(int i = 1; i <= n + 1; ++i){
  32.         dp[i][0] = 1;
  33.     }
  34.     for(int i = n; i >= 1; --i){
  35.         for(int t = 1; t <= tr; ++t){
  36.             if(t >= i){
  37.                 dp[i][t] = dp[i + 1][t - i] + dp[i + 1][t];
  38.             } else {
  39.                 dp[i][t] = dp[i + 1][t];
  40.             }
  41.         }
  42.     }
  43.     cout << dp[1][tr] / 2 << '\n';
  44.  
  45.     fclose(stdin);
  46.     fclose(stdout);
  47.     return 0;
  48. }
  49.  
RAW Paste Data