fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. #define ll long long
  8. #define debug(x) cout<<":["<<x<<"XE]"<<endl;
  9. #define debug2(x,y) cout<<":["<<x<<" "<<y<<"XE]"<<endl;
  10. #define mod 1000000007
  11. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  12.  
  13. ll l1[2000+5],n,x,dp[2005][2005];
  14.  
  15. int func(ll pos,ll sum)
  16. {
  17.     //debug2(pos,sum)
  18.     if(pos>n){
  19.         if(sum==x)return 1;
  20.         else return 0;
  21.     }
  22.     if(sum>=x){
  23.         if(sum==x)return 1;
  24.         else return 0;
  25.     }
  26.     if(dp[pos][sum]!=-1)return dp[pos][sum];
  27.  
  28.     ll x=func(1,sum);
  29.     ll z=func(pos,sum+l1[pos]);
  30.  
  31.     return dp[pos][sum]=(((x%mod)+(z%mod))%mod);
  32. }
  33.  
  34. int main()
  35. {
  36.     cin>>x;n=x;
  37.     for(int i=1;i<=n;i++){
  38.         l1[i]=i+2;
  39.         //cin>>l1[i];
  40.     }
  41.     memset(dp,-1,sizeof dp);
  42.     cout<<func(1,0);
  43. }
  44.  
Success #stdin #stdout 0.01s 35120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/sMDJaC
language:
C++14 (gcc 8.3)
created:
3 years 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!