Advertisement
Guest User

Untitled

a guest
Oct 21st, 2018
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #pragma comment(linker,"/STACK:128000000")
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cctype>
  5. #include <cstring>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <deque>
  9. #include <string>
  10. #include <vector>
  11. #include <queue>
  12. #include <stack>
  13. #include <map>
  14. #include <set>
  15. #include <unordered_set>
  16. #include <unordered_map>
  17. #include <utility>
  18. #include <algorithm>
  19. #include <tuple>
  20. #include <iostream>
  21. #include <random>
  22. #include <list>
  23. #include <iomanip>
  24. #include <assert.h>
  25. #include <random>
  26. #include <complex>
  27.  
  28. using namespace std;
  29.  
  30. typedef long long ll;
  31. typedef double ld;
  32. typedef vector<ll> vl;
  33. typedef vector<vl> vvl;
  34. typedef vector<int> vi;
  35. typedef vector<vi> vvi;
  36. typedef pair<int, int> pii;
  37. typedef pair<double, double> ptd;
  38.  
  39. const int inf = (int)1e9 + 1000;
  40. const ll infLL = 10000000000000001LL;
  41. const int mod = (int)1e9 + 7;
  42. const double eps = 1e-11;
  43. const double pi = 3.141592653589793;
  44. const int maxlen = (int)1e5 + 10;
  45. const int base = (int)1e9;
  46.  
  47. const int dd = (int)100 + 10;
  48.  
  49. #define ACCEPTED return 0;
  50. #define mp make_pair
  51. #define all(x) (x).begin(), (x).end()
  52. #define rall(x) (x).rbegin(), (x).rend()
  53. #define X first
  54. #define Y second
  55. #define optimize cin.sync_with_stdio(false);cout.sync_with_stdio(false);cin.tie(0);
  56.  
  57. ll dp[31][40];
  58.  
  59. int solve(int n, int x)
  60. {
  61.     if(dp[n][x]!=-1)
  62.         return dp[n][x];
  63.  
  64.     if(n==0)
  65.         return dp[n][x] = 1;
  66.  
  67.     if(x==1)
  68.         return dp[n][x]= (1<<n);
  69.  
  70.     if(x == 2)
  71.         return dp[n][x] = solve(n-1, x-1);
  72.  
  73.     return dp[n][x] = 2* solve(n-1, x-1);
  74.  
  75. }
  76.  
  77. int main()
  78. {
  79. #ifdef _DEBUG
  80.     freopen("input.txt", "rt", stdin);
  81.     freopen("output.txt", "wt", stdout);
  82. #endif
  83.  
  84.     optimize;
  85.  
  86.     int n;
  87.     cin >> n;
  88.  
  89.     memset(dp,-1,sizeof(dp));
  90.  
  91.     dp[1][2]=2;
  92.  
  93.     ll ans = solve(n,1);
  94.  
  95.     for(int x=2; x<=n+1; x++)
  96.         ans+= 2* solve(n,x);
  97.  
  98.     cout << ans;
  99.  
  100.     return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement