fork download
copy 
  1. #include <bits/stdc++.h>
  2. const int mod = 1e9+7;
  3. double begintime, endtime;
  4.  
  5. using namespace std;
  6. inline void CALC_TIME()
  7. {    
  8.     endtime = clock();
  9.     cout<<"\nexecution time : "<<(endtime-begintime+1)/1000<<" s";
  10. }
  11. int n, f[10008][10008];
  12. int dq(int i, int j)
  13. {
  14.     if(j >= n)return (j == n);
  15.     if(f[i][j] != -1)return f[i][j];
  16.     if(i+j > n)return f[i][j] = 0;
  17.     f[i][j] = dq(i+1, j)+dq(i+2, j+i);
  18.     if(f[i][j] >= mod)f[i][j] -= mod;
  19.     return f[i][j];
  20. }
  21. int main()
  22. {
  23.     begintime = clock();
  24.     ios_base::sync_with_stdio(0);
  25.     cin.tie(0);
  26.     cout.tie(0);
  27.     memset(f, -1, sizeof(f));
  28.     cin>>n;
  29.     cout<<dq(1, 0);
  30.     return 0;
  31. }
  32.  
Success #stdin #stdout 0.14s 394804KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/a0JyVK
language:
C++ (gcc 8.3)
created:
2 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!