TheAnshul

#Partition

Aug 22nd, 2018
579
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***** TheAnshul *****/
  2.  
  3. #include<bits/stdc++.h>
  4. #define ll          long long
  5. #define pb          push_back
  6. #define ppb         pop_back
  7. #define    endl        '\n'
  8. #define mii         map<ll int,ll int>
  9. #define msi         map<string,ll int>
  10. #define mis         map<ll int, string>
  11. #define rep(i,a,b)    for(ll int i=a;i<b;i++)
  12. #define mpi         map<pair<ll int,ll int>,ll int>
  13. #define pii         pair<ll int,ll int>
  14. #define vi          vector<ll int>
  15. #define vii         vector<pair<ll int, ll int>>
  16. #define vs          vector<string>
  17. #define all(a)      (a).begin(),(a).end()
  18. #define F           first
  19. #define S           second
  20. #define sz(x)       (ll int)x.size()
  21. #define hell        9799519364
  22. #define lbnd        lower_bound
  23. #define ubnd        upper_bound
  24. #define bs          binary_search
  25. #define mp          make_pair
  26. #define what_is(x)  cerr << #x << " is " << x << endl;
  27. using namespace std;
  28. #define N  7005
  29. ll dp[N][N];
  30. ll fun(ll n,ll m)
  31. {
  32.     if(n<=1)
  33.     {
  34.         return 1;
  35.     }
  36.     if(m>n)
  37.         return fun(n,n);
  38.     if(dp[n][m]!=-1)
  39.         return dp[n][m];
  40.     ll sum=0;
  41.     rep(k,1,m+1)
  42.     {
  43.         sum+=fun(n-k,k);
  44.         sum%=hell;
  45.     }
  46.     dp[n][m]=sum%hell;
  47.     return sum;
  48. }
  49. int main()
  50. {
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(0);
  53.     cout.tie(0);
  54.     int TESTS=1;
  55. //    cin>>TESTS;
  56.     while(TESTS--)
  57.     {
  58.         ll n;
  59.         cin>>n;
  60.         rep(i,0,n+2)
  61.         {
  62.             rep(j,0,n+2)
  63.             {
  64.                 dp[i][j]=-1;
  65.             }
  66.         }
  67.         cout<<fun(n,n);
  68.     }
  69.     return 0;
  70. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×